You mean something like this?

#! perl -slw
use strict;
$|++;

warn 'Start   : '.localtime() .$/;
my $data = do{ local $/; <> };

warn 'Read    : '.localtime() .$/;

my $lines = $data =~tr[\n][\n];
my $idx = chr(0) x ( 4 * $lines );
my( $i, $p ) = ( 1, 0 );
substr( $idx, 4*$i++, 4 ) = pack 'N', $p
    while $p = 1+index $data, $/, $p;

my $n = $lines;
for my $p ( 0 .. $n-1 ) {
    my $next = $p + int rand( $n-- );
    my $t = substr( $idx, $p*4, 4 );
    substr( $idx, $p*4, 4 ) = substr( $idx, $next*4, 4 );
    substr( $idx, $next*4, 4 ) = $t;
}

warn 'Shuffled: '.localtime().$/;

printf substr(
    $data,
    unpack( 'N', substr( $idx, 4*$_, 4 ) ),
    index( $data, $/, $_+1 ) - $_ + 1
) for 0 .. $lines;

warn 'Written : '.localtime().$/;
[download]