This version runs about 20% faster, probably since it slurps the file in all at once. It also doesn't care about collisions.

#!/usr/bin/perl -w
use strict;
my @lines = <>;
my @order = 
 sort { $a->[0] < $b->[0] }
 map { [ rand($#lines), $_ ] } (0..$#lines);
foreach my $line (@order)
{
 print $lines[$line->[1]]
}
[download]