I think this does it? And should handle your real data without problems.

Updated: see comment for the one-line change.

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

sub combs {
    my @inputs = @_;
    my @saved = my @index = map{ scalar $#$_ } @inputs;
    my $next = $#index;

    return sub{
        if( $index[ 0 ] == -1 ) {
            @index = @saved;
            return ();
        }
        my $rv = [ map{ $inputs[ $_ ][ $index[ $_ ] ] } 0 .. $#inputs 
+];
        if( $index[ $next ] ) {
            $index[ $next ]--;
        }
        else {
            $next-- until $index[ $next ] or $next == 0;
            $index[ $next++ ]--;
            @index[ $next .. $#index ] = @saved[ $next .. $#index ];
            $next = $#index;
        }
        return $rv;
    }
}

sub Cnr{
    my $n = shift;
    return [] unless $n--;
    map{
        my $x = $_;
        map{ [ $_[$x], @$_ ] } Cnr( $n, @_[ ($x + 1) .. $#_ ] );
    } 0 .. ($#_ - $n);
}

my $HoA = {
    flintstones        => [ "fred", "barney" ],
    jetsons            => [ "george", "jane"],
    domo               => [ "harry", "gato" ],
};

my $AoH = [
    map {
        my @array;
        my $iter = combs @{ $HoA }{ @$_ };
        while( my $vals = $iter->() ) {
            my %hash;
            @hash{ @$_ } = @$vals;
            push @array, \%hash;
        }
        @array;
    } Cnr scalar keys %{ $HoA }, keys %{ $HoA }

##    } Cnr 2, keys %{ $HoA } ##Replaced
];

print Dumper $AoH;

__END__
P:\test>504165
$VAR1 = [
          {
            'flintstones' => 'barney',
            'jetsons' => 'jane',
            'domo' => 'gato'
          },
          {
            'flintstones' => 'barney',
            'jetsons' => 'jane',
            'domo' => 'harry'
          },
          {
            'flintstones' => 'fred',
            'jetsons' => 'jane',
            'domo' => 'gato'
          },
          {
            'flintstones' => 'fred',
            'jetsons' => 'jane',
            'domo' => 'harry'
          },
          {
            'flintstones' => 'barney',
            'jetsons' => 'george',
            'domo' => 'gato'
          },
          {
            'flintstones' => 'barney',
            'jetsons' => 'george',
            'domo' => 'harry'
          },
          {
            'flintstones' => 'fred',
            'jetsons' => 'george',
            'domo' => 'gato'
          },
          {
            'flintstones' => 'fred',
            'jetsons' => 'george',
            'domo' => 'harry'
          }
        ];
[download]