I realize there is quite a difference between IaaS and PaaS, but there is some overlap. I'm particularly interested in getting the most number of "backend" server instances at the free tier (or for cheap). In particular for testing the scalability of an app I'm writing.
Redhat Openshift - 3 container instances ("gears") that can each run multiple items. Max 40,000 files, 1GB of storage, 512MB Memory, 250 threads per small gear. Appears to be a hybrid of PaaS & IaaS.
Amazon EC2 - Single linux microinstace. 64-bit 640mb server. 30Gb block storage, 5Gb "standard" storage, 100Mb nosql storage. strictly IaaS.
Amazon Beanstalk - PaaS that is billed based on the underlying EC2 usage consumed. Free tier has the same resources the free EC2 tier has.
Google App Engine - No backend instance provided for free, only frontend instances that run only for the duration of a web request.