I would suggest you to start with http://www.webfaction.com. It will cost you $9.50/month if you choose monthly payment schedule. It has enough flexibility to let you use most of the popular technologies(any software that runs on PHP, Python, Ruby, Perl or Java with MySql, Postgresql or sqlite).

If things go well and you can afford it, switch to Linode 512mb plan that will cost you $19/month and you will have full control over your development environment. (http://www.linode.com)

Need even more power? Keep adding more nodes to your linode account or switch to cloud hosting like Amazon EC2. :)