Check german hosters!! There you can very cheaply rent a box with pre-installed linux. You get the root-Password and can do with the box what you want, even install your own distribution. They call it "Rootserver". The catch is the traffic isnt as cheap, I think.