This will generate a million unique 128-bit random numbers in around 20 seconds, and happily goes up to 10 million (and I suspect very, very much higher, but I ran out of memory) without duplication.

If you want them hexified use unpack as in the commented out print statement.

#! perl -slw
use strict;
use Time::HiRes qw[ time ];
use Math::Random::MT qw[ rand srand ];

$| = 1;

our $MAX ||= 1000000;

srand( time );

my %hash;
for ( 1 .. $MAX ) {
    my $rand = pack 'N4', map{ rand 0xffffffff } 1..4;
    die "Got duplicate after $_ attempts" 
        if exists $hash{ $rand };
    $hash{ $rand } = ();
#    print unpack 'H*', $rand;
    printf "\r$_\t" unless $_ % 1000;    
}

__END__
[12:20:07.29] P:\test>417743 -MAX=1000000
1000000
[download]