It's possible, but I'm not sure the template is the best place to put logic into:
#!/usr/bin/perl
use warnings;
use strict;
use Template;
my $template = 'Template'->new;
my @reclist = ([1, 2, 'A', 4],
[3, 4, 'A', 5],
[5, 5, 'B', 2],
[6, 2, 'B', 3],
[1, 2, 'C', 2],
[2, 3, 'C', 2],
[1, 3, 'C', 1]);
$template->process(\( join "", <DATA>),
{reclist => \@reclist});
__DATA__
[% lastcat = "" %]
[% FOREACH catrec IN reclist %]
[% IF lastcat != catrec.2 %][% catrec.2 %][% lastcat = catrec.2 %][
+% END %]
[% FOREACH rec IN catrec %]
[% rec %]
[% END %]
[% END %]
map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]