AFAIK, Template Toolkit can be operated as pure-Perl (use the regular Template::Stash implementation instead of the Template::Stash::XS version). I'm not sure if it's 5.004 compatible, though...  but it shouldn't be too hard to find out by just trying (i.e. running its test suite).  (Update: just checked my older projects and found one using TT from the year 2000. I'm pretty sure it was deployed to a system running Perl at least as old as 5.005 (might even have been 5.004). IOW, your chances are not too bad...)

OTOH, it's not the fastest module if you're running plain CGI (as opposed to a persistent environment such as FastCGI or mod_perl) — quite a lot of code/files to be compiled on every request.