While everybody seems to be pointing to shuffling the list, how about randomizing the next element you're getting?

Something in the lines of (untested):

$stuff = [ 'cat', 'dog', 'pig', 'cow' ];

my %stuff map { $_ => 1 } @$stuff;
my @elements = keys $stuff;

for ($elements[int rand scalar @elements]) {
  $stuff{$_} = 0;
  @elements = grep $_, keys %stuff;

  # your code here, $_ being either a cat, a dog, etc.

}

for (keys %stuff) { $stuff{$_} = 1 }
[download]

Do notice: I just got up! :-) If it doesn't work, that why :-) And I'm pretty sure there are better ways of doing it :-)