Is this the sort of thing you're after (uses rand and map). Note that it'll reuse values from the hash. Not every one is guaranteed to be re-input into the new hash:

use warnings;
use strict;

use Data::Dumper;

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

my @vals = values %h;

my %new = map {$_ => $vals[int(rand(@vals))]} keys %h;

print Dumper \%new;
[download]

Output:

$VAR1 = {
          'c' => 2,
          'a' => 4,
          'd' => 3,
          'b' => 1
        };
[download]