Get a job that provides free colocation. Seriously. Get some old Dell PowerEdges and an external disk array off of Craigslist or eBay, then go to town.

Any service you pay to rent a machine or colo for you is going to be a rip off.

The alternative is to use something like Linode or similar to start off small, and scale if if necessary. Try and do a niche version of your grand idea.

The key is to test your ideas for as cheaply as possible and don't bleed cash for things you can do or arrange yourself. Good luck!