sub ikegami (@) {
    my @a=@_;
    my $i=@a;
    my $n;
    my $x;
    map +( $n=rand($i--), $x=$a[$n], $a[$n]=$a[$i] )[1], @a
}
[download]

           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%       --
[download]

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/ };
[download]

          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%       --
[download]

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.