Adding your optimization to BrowerUK's version, we get the best yet.
sub ikegami (@) {
my @a=@_;
my $i=@a;
my $n;
my $x;
map +( $n=rand($i), $x=$a[$n], $a[$n]=$a[$i] )[1], @a
}
Rate naive listutil runrig broweruk ikegami
naive 636/s  6% 19% 26% 37%
listutil 675/s 6%  14% 21% 33%
runrig 785/s 23% 16%  9% 22%
broweruk 859/s 35% 27% 9%  15%
ikegami 1010/s 59% 50% 29% 18% 
Of course, this doesn't always help. For example, try shuffling somewhat long strings.
our @data = map { 'x' x 1000 } 1..1000;
cmpthese 3, { map { $_ => "$_ \@data" } qw/naive listutil broweruk ru
+nrig ikegami/ };
Rate runrig naive ikegami listutil broweruk
runrig 118/s  10% 40% 43% 86%
naive 131/s 11%  34% 37% 85%
ikegami 197/s 68% 51%  5% 77%
listutil 207/s 76% 58% 5%  76%
broweruk 860/s 632% 558% 336% 315% 
Update: runrig pointed out that my shuffle was broken. I changed $a[$n] to $x=$a[$n] to fix it. It slowed down my solution, but not by much.
