I totally agree. Luckily more and more VPN providers accept Bitcoin payment, so that problem is solved (if you don't connect your wallet to your ID, that is) [1]. I think the more challenging part is not sending personally identifiable information through your VPN or encrypt it properly. Much of the Web is architected to identify you based on the most mundane technical information, like your browser string, cookies, the way you type or those little data leeks that happen here and there.
[1] http://www.bestvpnservice.com/blog/vpn-providers-with-bitcoi...
ps. No, I don't use a VPN. But I like to stay informed.