"I could sorta do it with a pair of arrays and an index variable, but I like being able to reference an element by its key."

Liking and having are two different things ... if you really need to do so, then Tie::IxHash will do the trick. But if you don't, then maybe you simply need to rethink your datastructure. For example, you can store a list of hashes in an array:

my @people = (
   { name => 'John Doe',    age => 30 },
   { name => 'Sally Smith', age => 42 },
);
[download]

Now the order is preserved, but you can't perform a O(1) lookup anymore ... but do you really need to? For the record, i have yet to need Tie::IxHash, but them's just my needs. ;)