#!/usr/bin/perl -w
use strict;
my(%hash,$i);
@hash{map($i++.":$_", <>)} = ();
print "$_\n" for map /^\d+:(.*)/, keys %hash;
[download]

NB: the $i++ and regex trickery is necessary to preserve identical lines.

Update: Since the above code will produce the same "randomized" file every time you run it with the same input data:

#!/usr/bin/perl -w
use strict;
my(%hash,$i);
@hash{map join(":", $i++, int rand $i, $_), <>} = ();
print "$_\n" for map /^\d+:\d+:(.*)/, keys %hash;
[download]

Which I guess was not the point, since we're back to using rand()
____________
Makeshifts last the longest.