#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my %hash = ( "a" => 1,
	     "b" => 2,
	     "c" => 3,
	     "d" => 4
    );

# Export keys from the hash
my @keys = keys %hash;

# Export values from the hash
my @values = values %hash;

my %new_hash;
for ( 0 .. $#keys ) {
    $new_hash{splice @keys, rand @keys, 1} = splice @values, rand @values, 1;
}

print Dumper \%new_hash;

__DATA__

$ perl test.pl
$VAR1 = {
          'a' => 1,
          'b' => 2,
          'c' => 3,
          'd' => 4
        };