If I understand you correctly, you want to produce all possible combinations of elements from your arrays. Maybe it would be easier to generate indexes for arrays separately. It's like an odometer:

0 0 0
1 0 0
2 0 0
3 0 0
0 1 0
0 2 0
0 3 0
0 0 1
1 0 1
2 0 1
3 0 1
0 1 1
0 2 1
(etc)
[download]

So, your odometer looks like this (at first):

my @odometer = (0, 0, 0);
[download]

And you use it like this:

while_odometer_has_not_run_to_completion... {
  $id2++;
  (
    $data{$id}{$id2}{'key1'},
    $data{$id}{$id2}{'key2'},
    $data{$id}{$id2}{'key3'}, 
  )
    = 
  (
    $hash{$id}{'key1'}[ $odometer[0] ],
    $hash{$id}{'key2'}[ $odometer[1] ],
    $hash{$id}{'key3'}[ $odometer[2] ],
  );
  next_odometer( \@odometer );
}
[download]

...or something like that...