Shuffle based on the first field? Why not just shuffle the entire file? Here is a very consise way of doing so using a couple of useful CPAN modules, Tie::File so we can access the file as an array and List::Util which contains a shuffle sub (which is a Fisher-Yates implementation, i believe) ready to go:

use strict;
use warnings;
use Tie::File;
use List::Util qw(shuffle);

my @file;
tie @file, 'Tie::File', 'foo.dat' or die $!;
@file = shuffle(@file);
[download]

jeffa

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)