You can use rand within the sort code.

@stuff = qw[ cat dog pig cow ]; 
print "$_\n" for sort { rand() <=> rand() } @stuff
[download]

Update. I have the (theoretical) feeling that this trick may cause an infinite loop when used with a large array, but a few tests I did returned nothing suspicious.

HTH