I would look into either Google App Engine or Amazon Web Services. They both give you free allotment of usage per month and if you go over then you start paying, chances are you wont get past the free tier for a while.
AWS is a bit more mature than GAE currently and seemed to be a bit easier to implement that GAE was when I was researching them