It's important to note that this is not a perl problem, any more than the fact that your CGI programs written in C, or Python, or Scheme, or Fortran, or INTERCAL don't time out. It is well and truly a server management issue, and if your webserver (or whatever server software, or OS, it is) doesn't support time quotas on processes then you have issues very much apart from any capabilities of perl. From your description, I fully expect you're screwed no matter what you do, since your hosting provider looks clueless.
in reply to Win32 Hosting companies not supporting Perl
Having said that, Parrot will allow time, memory, and IO quotas, with privilege based overrides, on individual interpreters. Assuming whatever firing off parrot sets those quotas. They certainly won't be on by default, as that's very much the wrong default, but it will be settable.
This probably won't help you, given the issue as described (since if your service provider's not even putting generic timeouts on spawned child CGI processes I expect there's little to no chance they'd configure things right), but the option will certainly be available.