I live at a college at University of Queensland, where we have pretty restrictive internet access. Data can be unrestricted, charged at 15c/MB (AUD), or through a HTTP Proxy at a much cheaper rate.
In order to get around this, I put my traffic through a HTTP proxy through a VPN to a remote host.
There are a few things you should be aware of before you do this:
In order to tunnel the VPN, I used HTTP Tunnel. This software has both a Windows and Unix client/server, and will allow you to tunnel arbitrary connections though a HTTP proxy, with support for proxy HTTP authentication.
OpenVPN is an Open Source VPN solution, with both Windows/Linux clients/servers. It has the ability to work through a single TCP connection, allowing us to tunnel it through the proxy.
Update: I received word from an anonymous source that OpenVPN can now perform tunnelling through the HTTP proxy for you. The relevant config lines for OpenVPN you should look at are:
http-proxy proxyserver 8080
http-proxy-option AGENT Mozilla/5.0+(Windows;+U;+Windows+NT+5.0;+en-GB;+rv:1.7.6)+Gecko/20050226+Firefox/1.0.1
Ensure Universal TUN support is built into the kernel.
Run OpenVPN, first instanciating a daemon without encryption. Once you get this working, work your way up to using RSA encryption, or stick with a static key.
Assuming you will use the IP addresses 10.0.0.1 for the server, and 10.0.0.2 for the client on the VPN, this command will open a openvpn daemon instance:
openvpn --proto tcp-server --port 5000 --dev tun1 --ifconfig 10.0.0.1 10.0.0.2 --verb 8
Run HTTP tunnel on the server (using the "hts" daemon), to listen on a port, and forward it to the VPN daemon (by default this should be 127.0.0.1:5000). I used port 81, as the proxy will allow connections to port 79, 80, 81, etc.
The command to do this, looks like:
hts -F localhost:5000 81
Run HTTP tunnel on the client (using the "htc" client), to listen on a port, and forward it to the htc daemon on the server.
htc -P proxyhost:proxyport -A "username:password" -F 5000 htshost:htsport
Run OpenVPN, first instanciating a client without encryption to the htc process. Assuming you will use the IP addresses 10.0.0.1 for the server, and 10.0.0.2 for the client on the VPN, this command will open a OpenVPN client instance:
openvpn --proto tcp-client --dev tun1 --ifconfig 10.0.0.2 10.0.0.1 --verb 8 --remote 127.0.0.1
With some luck, when you ping the server from the client over the VPN, we should get data flow:
If you get a reply, you should now look into using encryption for the VPN.
There are many HOWTOs available for setting up NAT. As such, it isn't covered here.