On a 64-bit system with a modern perl, it uses about 3.5Gb, assuming that the strings and the array were created in the most efficient way possible.

As much as that? I based my estimate upon this (running 5.10.1 64-bit):

c:\test>p1
[0] Perl> 
sub shuffle { 
    my $r = shift; 
    for ( 0 .. $#$r ) { 
        my $a = $_ + rand( @$r - $_ ); 
        my $t = $r->[ $a ]; 
        $r->[ $a ] = $r->[ $_ ]; 
        $r->[ $_ ] = $t; 
    }; 
};;

[0] Perl> @a = 1 .. 1e6;;
[0] Perl> push @a, @a;;
[0] Perl> push @a, @a;;
[0] Perl> push @a, @a;;
[0] Perl> push @a, @a;;

[0] Perl> $t = time; shuffle \@a; print time - $t;;
20.9429998397827

[0] Perl> print total_size \@a;;
518218064
[download]

That's 16 million integers occupying just under 500MB being shuffled in 20 seconds.

I reasoned that 3 times that gives 48M in 1.5GB. Then replace the ints with the pointers and add 48mx20 (rounded up to 24) = 1.01GB for the strings themselves. gives 2.5GB total; and around 60 seconds to shuffle. Did I miss something?

Another possibility is to use a single large string, divided into blocks of 20 chars, to avoid the overhead of the array and SVs; then access individual elements using substr().

I had similar thoughts. On the basis of the single pair of numbers the OP gave as an example, it looks like floats would be sufficient precision for his purposes. In which case, a packed string shuffled with substr seemed possible:

c:\test>p1
[0] Perl> sub shuffle { 
    my $r = shift; 
    my $n = length( $$r ) / 8; 
    for ( 0 .. $n ) { 
        my $a = $_ + rand( $n - $_ ); 
        my $t = substr $$r, $a, 8; 
        substr $$r, $a, 8, substr $$r, $_, 8; 
        substr $$r, $_, 8, $t; 
    }; 
};;

[0] Perl> $a = pack 'f*', map -1e5 + rand(1e9), 1 .. 1e6;;
[0] Perl> $a x= 96;;

[0] Perl> print length $a;;
384000000

[0] Perl> $t = time; shuffle \$a; print time - $t;;
59.6950001716614
[download]

It really rather surprised me that the shuffle time was so close to my estimate for the array of strings. (Despite needing 4 substrs per.)