I'd be inclined to turn the problem around. Build a list of all the ogjects that are in the queue. Randomise the queue. Draw the objects out one at a time.

If the objects need to know what their position in the queue is run over the queue after it's been randomised and tell the objects what their turn number is.

Super Search for titles containing "random array" in SoPW for a huge number of threads asking how to generate a randomised list or how to pick a random entry from a list.

Update: A simple way to do it is:

my $array;
my @queue;

#gen objects
push @$array, SOMECLASS->new() for 1..100;

#generate random ordered queue
push @queue, splice @array, int rand @array, 1 while @array;

#process
$_->dosomething () foreach @queue;
[download]

The down side is you lose the original ordering and splicing stuff randomly out of a huge list may slow things down a little. For a small list or occasionally it shouldn't be a problem.