Not sure about fastcgi, but http://rootr.net is the host I use, and my
site uses eRuby and amrita.  I've got nothing but good things to say
about Rootroute.  They've always put up with my shenanigans, and will
generally install any Ruby library you ask them to as long as it's not
going to destroy their servers.