As a bit of a golf Challenge:

$r=(grep!$$_++,@a)[rand@a] #evil
[download]

That probably doesn't help you so much though, does it? Lets work through the first one, and re-write it a bit clearer as we go along.

# create a counter to store the number of times the variable has
# been encountered.
my %counts; 

while (1)
{
    my %h = %counts;

# Allow only the elements that haven't been seen yet.  Check the 
# perlfaq for more details
    my @unique = grep {!$h{$_}++} @array; 

# if @unique has no elements, there aren't any non-duplicates left
    last unless (@unique);

# grab a random index
    my $random_index = int(rand(@unique)); 

# get a random element
    my $random_element = $unique[$random_index];
    print "Random non duplicate element is: ", $random_element, "\n";

# add the element to the counter so that it doesn't get set
    $counts{$random_element}++;
}
[download]

Thats a bit less efficient than the first example, but much more readable. If you have any questions about it, just respond.