Slash.
It should answer all of your needs, at least with regards to being scalable for heavily-hit sites (duh ;-)).

Personally I've worked with HTML::Template and loved it - very easy, very maintainable (seperation of HTML from Perl code), but I can't say anything about how well it scales for sites that are heavily hit.