What about creating your own randomness algorithm? They're pretty simple to write and you don't need all the crazy stuff that most randomness algorithms need. Something like:

sub next_random_number {
    my ($prev_number) = @_;
    $prev_number ||= 0;

    return ($prev_number + 14412312 ) / 123142131;
}
[download]

Now, that obviously wouldn't be good enough. But, you just need to generate and store the algorithm that comes up with the list, whatever that is.

An alternative which comes to mind (given that you're only doing this every so often) is to spawn a new process to come up with the shuffled list and let that process have its random number generator set. That way, the parent process is still fine, but you're able to set the stuff properly.