Many hosting services do offer FastCGI, and there are several ways that (e.g.) the Apache server can offer it, one of which appears to be distinctly tilted toward the needs of hosting companies. The only way to know which options can be made available to you is, of course, to ask them directly.
I like to design web servers to use Plack, which gives the ability to choose which deployment strategy works best for you, and to change that strategy with little or no impact to your code. Plack “abstracts away” such differences and does an excellent job of it.