Скажите, установлен ли на сервер 1 FastCGI?
mod_cgi - есть
mod_fastcgi - нету
Если нет то как можно ускорить выполнение cgi скриптов, неговоря уже о perl?

Нет.
На шаред-хостинге - никак.
Если, например. VDS возьмете - там можете устанавливать что угодно, и FastCGI в том числе.