use List::Util qw(shuffle);
...
foreach my $k (shuffle keys %foo) {
...
}

##</code><code>##

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

##</code><code>##

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