Vultr (http://www.vultr.com/?ref=6979836) allows you to pay with bitcoin, making it more difficult to trace you
...but they require a valid credit card/paypal deposit beforehand, which kills the whole point.
edit: there's a list of providers allowing only bitcoin as payment method: http://cryto.net/~joepie91/bitcoinvps.html