How about something like...

my %seen=();
$array_size = @array;

$index = "";
until ($index ne "") {
    my $dbl_chk = keys %seen;
    if ($dbl_chk == $array_size) { #Every array element has been seen 
+once.
        %seen = (); #start over!
        }
    my $new = int(rand($array_size));
    if (!(exists($seen{$new}))) {
        $seen{$new} = 1;
        $index = $new;
        }
    }
[download]

If you need to know which ones have been seen already:

@seen = keys %seen; #array index of "seen" values.
[download]

or what if the random number generator continues to produce "seen" index values
--you're either very unlucky, or you need a better random number generator.

update in the future, it would probably serve me better to read the entire post. The "shuffle" is a better answer than mine. Although, on large arrays it might be faster just to read elements until you find an unread one than do a random sort. I'm not sure.