Seems to me that your laying your one-to-many data as many-to-one. I think I'd lay it out and populate the hash this way. Nested maps aren't to everyones tastes, but they make light work of the job at hand.

#! perl -slw
use strict;
use Data::Dumper;

my %hash = map{ local $a=$_; map{ $_ => $a->[0] } @{$a->[1]} } (
    [ value_for_keys_1_2_3 => [ qw[key1 key2 key3] ] ],
    [ value_for_keys_4_5_6 => [ qw[key4 key5 key6] ] ],
    [ value_for_keys_7_8_9 => [ qw[key7 key8 key9] ] ],
);

print Dumper \%hash;
__END__
c:\test>230905
$VAR1 = {
          'key7' => 'value_for_keys_7_8_9',
          'key8' => 'value_for_keys_7_8_9',
          'key1' => 'value_for_keys_1_2_3',
          'key9' => 'value_for_keys_7_8_9',
          'key2' => 'value_for_keys_1_2_3',
          'key3' => 'value_for_keys_1_2_3',
          'key4' => 'value_for_keys_4_5_6',
          'key5' => 'value_for_keys_4_5_6',
          'key6' => 'value_for_keys_4_5_6'
        };
c:\test>
[download]