I don't know how invested you are in HTML::Template, if you're pretty heavy into it than you can probabbly ignore the rest of this post. Fyi I think the only real way to do this with HTML::TEmplate is the first method you specified.
Stuff like this is one of the main reasons I ended up switching from HTML::Template to Template::Toolkit. With template toolkit you can do something like

[% # THis is in templatelib.tt %]
[% MACRO date_template(parm1, parm2, parm3) BLOCK %]
  [% SWITCH parm1 %]
    [% CASE "value 1" %]
      display this way
    [% CASE "value 2" %]
      display other way
    [% CASE DEFAULT %]
      display default way
  [% END %]
[% END %]
[download]

Your main template could look something like

[% # this is foo.tt %]
[% PROCESS templatelib.tt %]
[% date_template(parm_from_script, "foo", "bar") %]
[download]

your perl would look something like

my $template = Template->new();

my $t_vars = {
   parm_from_script => "value 1",
   other_stuff => "mmmm donuts",
};

$template->process("foo.tt", $t_vars) ||
   die $template->error();
[download]

Granted, there is now "code" inside the html, but it's still all display logic. It's not the processing logic. I tend to make the line between perl/templates in that perl will handle anything that's not strictly for display while the templates will handle everything else. People disagree with this and they're right too. :P