I am thinking of starting a website, but for it to work, I need a ruby script constantly running in the background.
Can you recommend any web hosts that allow this?
As mootinator said, any host which allows you to run cron jobs should allow it as long as your process isn't against their TOS. With a VPS or dedicated server you can pretty much run whatever you want, but even most decent shared hosts will allow you to run background processes as long as they're not too resource intensive.
For example, DreamHost allows you to run persistent background processes on their shared hosting so long as they aren't disruptive and don't involve IRC, bittorrent, or streaming media. Otherwise, you need to switch to a VPS plan.