I've search CPAN for distributions with Template in the name, and clicked on the "Perl/Platform Version Matrix" link for a dozen distribution, and the oldest test reports where from perl-5.005 (heck, I silently curse Slaven each time he sends me FAIL report with his ancient 5.005).

So your best bet for getting libraries for an eleven year old perl would be to look on backpan for older modules. For example here you can find old versions of HTML::Template, and try which one work on your system.