If you go the DIY route, check out these shell scripts for installing+configuring PPTP and OpenVPN servers: https://github.com/cwaffles
If you're not sure where to get a VPS suitable for VPN service, look at lowendstock.com or lowendbox.com or lowendtalk.com/categories/offers
If you choose a VPS provider which uses OpenVZ for virtualisation, make sure they let you enable TUN/TAP and PPP from the control panel. Almost all do. Some mention it explicitly.
If you want a cheap non-DIY solution look at http://vpn.sh/
I've actually ran a sniffer on a VPN service before and I could monitor other user's traffic (although that is of limited use as I couldn't MITM them nor decrypt HTTPS traffic).
Regardless I'd be looking for an OpenVPN provider if you can find one. By far the more flexible type of VPN since it can be accessed over a lot of free wifi which offers only HTTP/HTTPS traffic.