If I have an open mesh wireless network (or, really, any open access network) and I want to keep the network open access: that is, anyone with the right hardware should be able to connect and talk to other computers on the network, but I want to require authentication for Internet access, what should I use?
PPP seems like the right tool for the job. I thought at first PPPoE, but I've been informed that probably cannot work over wireless. So then I have to tunnel using PPTP? I'm trying to minimize overhead, which is why I initially shied away from PPTP/OpenVPN solutions.
If IPSec can be run in tunnel mode without encryption that may also achieve this, I think.
Are there other good solutions that I'm not thinking of?
Note that I do not consider using an HTTP proxy server or the other sorts of weird hacks you often see at hotel wifi acceptable solutions.
If possible I would like to make it so that people who authenticate are able to have a public IP, and not just sit behind a NAT.
While some sort of VPN may work for this, it's probably overkill. Sounds like you just need a captive portal page with some sort of authentication back-end, possibly radius. I frequently use pfSense for NAT/firewall/routing on my networks, and it includes a very easy-to-configure captive portal system. Chillispot is another open-source option.
Another option which is used in larger networks is 802.1x. You can use it with radius based on either linux freeradius or windows. You can then integrate with ldap or aduc depending on your environment.