Just did a quick search for ROR hosts and the first that came up was VPSLink. I've never used them so do your own due diligence. I would do some searches and then start contacting any that catch your eye.
Well you can run a Ruby stack on any VPS obviously. I suppose there are multiple approaches:
1) blank VPS, install Ruby yourself (any provider will do)
2) use pre-built Ruby VPS image/template (check with provider for templates)
3) use Ruby applications along with standard hosting stack (use cPanel, for example)