I'm not sure I understand your reservations about hashes, or what you mean by "precomputing hash keys" and extra memory.

The only thing you lose by moving to a hash is the ordering of the keys, but you can get that back:

my $question = {
    descriptions => {
        m => "male",
        f => "female",
        o => "other"
    },
    choices => [ qw/m f o/ ]
}
[download]

Then to generate the HTML in the right order is not so bad (not that I'm a big fan of this -- you should be using a templating system anyway):

for my $choice ( @{ $question->{choices} } ) {
    my $text = $question->{descriptions}{$choice};
    print qq[<option value="$choice">$text</option>\n];
}
[download]

And validating choices becomes trivial:

$valid = exists $question->{descriptions}{$answer};
[download]

Anyway, having an array of arrays, with inner arrays having just 2 items, is a good sign that a hash (or certainly a relation matrix) might be in order.