I have three clients on inexpensive hosting plans using FastCGI and have not run into any issues due to FastCGI itself. These are all low traffic sites where Mongrel was not necessary.
Will rails + fast.cgi provide a good experience for a user
It all depends on what you're trying to do. If you're going to build a site where users will uploading and playing video then no FastCGI is not a good choice.
or should I choose, in this scenario, php + my-favorite-framework as platform
You always choose the right tool for the job. Without any details on what you are trying to build I'm not sure anyone here will be able to tell you how to build it.