For static websites, Github Pages is free, nearlyfreespeech is very cheap. For full-blown web apps, didn't you hear the guy? GAE has a pretty generous free tier to test out stuff. So does Heroku, and it's way more user friendly. I still prefer GAE because I can use Google's tools. If you want to rent instances, you're going to have to pay from the beginning afaik. AWS and GCE are the usual suspects here.
I didn't use GAE that much, I only know that whenever I needed to try something for free, Heroku's plugin architecture comes in handy, since most addons have free tiers. They even support neo4j, an amazing graph database I just started playing with (and it's in beta, so they give a shitload of space for free).
https://pages.github.com/
https://www.nearlyfreespeech.net/
https://developers.google.com/appengine/
http://heroku.com/