my $hashref = {
  1 => [Frog,      Fuzzy,   A, other_stuff],
  2 => [Frog,      Fuzzy,   '', other_stuff],
  3 => [Toad,      Zola,    Q, other_stuff],
  4 => [Frogger,   Anthony, J, other_stuff],
  5 => [Frog-Toad, Berl,    G, other_stuff]
};

use Data::Sorting 'sort_function';

my $sort_function = sort_function( map { my $x = $_; 
    sub { $hashref->{ $_[0] }->[ $x ] }
  } 0, 1, 2);

my @keys = $sort_function->( keys %$hashref );

print join ', ', @keys;