The following sub make a closure with the given array. Every time the closure is called it return a random element different from the previous. It also have no loops so it's fast. Note: it will never start with the first element.

sub RnR
{
        push my @list, @_;
        return sub
        {
                my $r = 1 + int rand(@list-1);

                # swap [0] with [$r]
                my $t = $list[$r];
                $list[$r] = $list[0];
                $list[0] = $t;

                return $t;
        }
}

# usage
my $rnr = RnR(qw(a b c d e f g));
print "next :", $rnr->(), "\n" for (1..20);
[download]

If instead you can't keep the script persistent to each call and you want no repetition, then there is no solution.
BTW Iff you have a progressive number which increment by one for every call (this can be done on client side, or using the time iff the requests are periodic) you can split the data in two sets (or more). You can then return a random one from the first set if the progressive is even, and a random one from the second set if it's odd.

Oha