You cannot shuffle keys because keys do not have an order. You can accomplish what you ask by shuffling the values.

use strict;
use warnings;
use List::Util qw(shuffle);
use Data::Dumper;
my %hash = (
   "a" => 1,
   "b" => 2,
   "c" => 3,
   "d" => 4
);
@hash{ keys %hash } = shuffle values %hash;

print Dumper(\%hash);

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

I am curious why you want to do this.