I did some quick research on several vendors and sumarizd by findings here:
For me, Google AppEngine makes most sense. You pay nothing for up-to 5 million page-views per month. The only problem, albeit a major one, is that it's only python. It's not a problem for me though since I know python.
Other providers are way too expensive. Look at engineyard.com, $400 per month get you a meager 760Mb ram, only 250GB transfer. Someone must be out of his mind to purchase it.
For those who don't go with AppEngine, I would say it's best to just get a VPS. You can do whatever you want with VPS just like a dedicated server. And it's cheap, you can easily find a 512M ram VPS with plenty of diskspace and bandwidth for less than $50, that's all you pay. (Just make sure your VPS is Xen based, not Virtuozzo/OpenVZ based, as they allow ram bursting, which means you will NOT get your ram when you really need it, as other users on the same host machine as you stole it.)