WebFaction is quite popular among the Python and Django community, recently it has simplified Rails and other Ruby web frameworks.
Unlike other Web hosts they do not bundle a domain name, but these can be bought quite cheaply from www.gandi.net. I would then forward the MX records to google and get a gmail handler for your mail. You do not have to get a domain straight away by default you can use username.webfactional.com
First I had to install Passenger (I think this is also called Rack), I set the name to passenger.
This means that if you ssh/sftp/ftp into your account you will see ~/webapps/passenger/
Then I entered the Websites section then created a new subdomain devel.username.webfactional.com and set this to be type:passenger location:/
I had to wait sometime before these setting became active.
There article can then be followed for setting up a basic Sinatra over passenger (Rack).
NB: for a sinatra app you only need to install Passenger (not rails) and gem install sinatra (plus sequel / activerecord etc).