#!/usr/bin/perl
use strict;
use warnings;
use Set::CrossProduct;

my %hash=('ID' => {
                  'key1' => ['key1_val1', 'key1_val2'],
                  'key2' => ['key2_val1', 'key2_val2'],
                  'key3' => ['one', 'two']
                  }
          );

for my $id (keys %hash) {
    my $key3 = delete $hash{$id}{key3};
    my @data = values %{ $hash{$id} };
    
    my $cp = Set::CrossProduct->new( \@data );
    
    my $i = 1;
    while( my $array_ref = $cp->get ) {
        print join( " ", $id, $i++, @$array_ref ), "\n";
    }
    
    print "@$key3\n";
}
[download]

ID 1 key2_val1 key1_val1
ID 2 key2_val1 key1_val2
ID 3 key2_val2 key1_val1
ID 4 key2_val2 key1_val2
one two
[download]