I think what you intend is this:

sub NEXTKEY
{
     my ($self, $lastkey) = @_;  # $lastkey isn't used?
     while (my $key = $KEYS[$self->{INDEX}++])
     {
          if ($key ne $self->{FIRSTKEY})
          {
               return $key;
          }
     }
}
[download]

You need a loop structure to loop, although redo can be teased to do some odd things.