There is a deprecated data structure called a pseudohash which is ideal for this, whatever its other disadvantages. To pseudohashify your AoA:

my $AoA = [ [1..3], [7..9], [3..5] ];

my $row_labels = { foo => 1, bar => 2, baz => 3 };
my $col_labels = { do => 1, re => 2, mi => 3 };
unshift @$_, $col_labels for @$AoA;
unshift @$AoA, $row_labels;

print $AoA->{'foo'}{'re'}, $/;
print $AoA->[1][2], $/;
[download]

This is not well-regarded these days, but it will do the job. Don't rely on it being available in a year or two.

After Compline,
Zaxo