I'm the author of Data::Sorting, and I can report that it doesn't really handle this situation well. (If you were sorting the arrays themselves, Data::Sorting would let you express it very concisely, but for sorting the keys by the values it's not so great.)

You can get something close to what you want, but as the other solutions here have shown, it may be easier to do the sorting yourself.

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;
[download]