> Impossible on OS X and Linux without shelling out $$$.

I've never used it, so I can't endorse it, but this was among the first results in a google search for "linux per application firewall":

http://douaneapp.com/

I guess there has been progress in this space since you last looked.

There is also SELinux controls that can be used... so -IIRC- you could create a per-app firewall with that. :) I would be slightly surprised if there weren't pretty reasonable GUIs for managing such SELinux rules.