AppFog has a free tier under 2GB Ram, 50 GB bandwith and 100 Mb database.
I think it's not the cheapest but it gives you some time before you have to invest. I didn't used it in production, but for testing it was good enough. I could deploy a scala-lift app in a not too hard way. (1 GB ram, 2-3 hours thinking and one af push, but I was not familiar with lift or clouds at all)