Perhaps you could store the value of the key in the hash based index as the first element of the data its pointing to? That way the first element of each of the original arrays would be the key of the hash used to access it. The key can be used to get the array or vice versa.
use strict;
my @ref_array = ([state,pointer],[state,pointer],[state,pointer]);
my $i = -1;
my %key_index = map($i++; unshift(@{$_},$i); $i,\$_;)@ref_array;
Of course I have not tested this (my BSD partition is mad at me presently). But I think the logic will satisfy your 3 requirements.
UPDATE:(Aug.16th)
Just a quick note the my @ref_array illustrated above was meant to represent the original items mentioned in the original post. The [state,pointer] is in reference to another post in which the structure of the original items was explained...
my apologies for the confusion.
example below:
This is what I was talking about.
%key_index items in anon.arrays
(@ref_array in my post)
{ 0 => \itemA } [ 0, status, dataA ]
{ 1 => \itemB } [ 1, status, dataB ]
{ 2 => \itemC } [ 2, status, dataC ]
this way the key (0-2 in the example) is stored with the original data. that way you can always get the key of the index_hash from the element itself. The shuffling should not matter at that point.