You may also want to check out CGI::FastTemplate. I've been quite pleased with it. I agree with lhoward - if you're paying for webhosting, you should be able to specify a few perl modules for your site(s) - if your current hosting company won't comply, you should be able to find one that does pretty easily.
You see, the main idea behind the templates is to allow my designers to keep to HTML and not have to even think about splitting a file up into head.tpl, foot.tpl. row.tpl and so forth. Come to think of it, I don't think I would use it even if I where doing all of the work myself because the of the template mess you might get into when doing a complex designed site. Keeping track of each tpl file would become, as lhoward put it, a maintenance nightmare.