When I'm on a public network that I don't trust, I use a combination of ConnectBot and ProxyDroid (with "Global Proxy" enabled) to tunnel my phone's traffic through a trusted server that I control. However, I have to set that all up manually, and I'm sure plenty of other data leaks out around that tunnel (at the very least, apps will check in between the time I connect to a network and the time I set up the tunnel). Also, the process is involved enough that I usually only go through it when I'm on a public network and I get SSL errors from the browser telling me google.com is using a certificate signed by GoDaddy.
I'd like to set something up that smooths the process out a bit, such that a tunnel is automatically established whenever I connect to a network, all traffic is routed through it, and apps aren't able to connect to the Internet unless the tunnel is open (very important). Obviously, it should verify the authenticity of the server before connecting (though I haven't seen a VPN that doesn't). I'd like something that uses SSH since that's the simplest to set up, but anything will do. What sorts of solutions like this are out there? My server runs Ubuntu 12.04, and I can install extra software on it if needed.
Again, the most important part here is that no app can access the network unless it's going through the tunnel, and if the tunnel hasn't been established yet, no traffic escapes. Obviously, the one exception would need to be whatever app is actually making the initial connection to establish the tunnel.
I'm currently using a rooted HTC Incredible running CyanogenMod 7. I'm in the market for a new phone though, so if anyone knows of any solutions that require something newer than Android 2.3, those would be welcome as well.