I use AFwall (which built upon Droidwall).
I'm not sure if it meets your definition of a real firewall or not, but I like it.
1 - very simple interface - set it up to allow or block each application individually.
2- No overhead of a running program or service (it modifies iptables, whatever that means).
3 - Logging capability to identify what was blocked.
4 - Free.
Tough to know. Droidwall had a few known vulnerabilities (like a time window during the reboot period when applications were not blocked) that were fixed by AFwall. I don't think any vulnerabilities have been identified for AFwall yet... yet being the operative word.
There is also Pdroid which controls other privacy sensitive features besides internet access. Looks interesting and useful. But the installation procedure is so complicated that I haven't tried it.