｢安い｣が個人ﾚﾍﾞﾙの安さなのか､法人なのかで変わってきますが…｡
個人ﾚﾍﾞﾙで言うなら､

◯Amazon EC2
ｸﾗｳﾄﾞの中ではあまり安いとは言えませんが､一年間限定で無料で使えるﾌﾟﾗﾝがあります｡
http://blogs.itmedia.co.jp/saito/2010/10/amazon-ec21-574.html

◯さくらのVPS
月1000円程度から利用できます｡割りと大手なので安心｡
http://vps.sakura.ad.jp/

◯DTI VPS
月500円程度から｡最近重いですが安いです｡
http://dream.jp/vps/

あたりでしょうか｡
あとは普通にVPS等でGoogleを検索すれば色々出てくると思います｡
お名前とかSaaSesとかもろもろ｡


ｸﾗｳﾄﾞ､VPSはどこもﾃﾞｨｽｸへの書き込みが遅いです｡
PVもですがどの程度ﾃﾞｰﾀの更新があるかという部分がﾎﾟｲﾝﾄかもしれないですね｡

最近はお試し期間があったりしますから､実際にRailsを入れて試してから契約するのが
確実かもしれません｡