There have been a few new hosting options lately - it's really getting very cheap to host a server. Case in point: Digital Ocean, which provides $5 root-access IP addresses. Not much storage, granted (20 gig), but the servers in question are blazingly fast, SSD drives and multiple cores for a little more money. Outgoing bandwidth is measured in terabytes, and incoming is not metered at all.
You can set up new servers with an API call.
And that's just one such hosting company. I'm going to start tracking the ones I find under this "hosting" tag. Right now I'm paying $60 a month for a dedicated server that's, what, seven years old and feeling it? That's just money wasted these days.
Another cheap hosting alternative I've seen lately is Uberspace.de, remarkable for being in Germany, which could be quite useful.