Possibly not the best solution, but you could always shim a coderef into $Template::Stash::LIST_OPS which takes an argument as to the direction. Untested but along these lines

$Template::Stash::LIST_OPS->{'sortplus'} = sub {
  my( $aref, $dir ) = @_;
  local *S = $dir ? sub { $a <=> $b } : sub { $b <=> $a };

  return sort 'S', @{$aref};
}
__END__
[% FOREACH key_1 IN my_hash.keys.sortplus( reverse_flag ) %]
  [% FOREACH key_2 in my_hash.$key_1.keys.sortplus( reverse_flag ) %]
    Yadda yadda yadda.
  [% END %]
[% END %]
[download]