sub delete_first(\%) 
{
  my $hash = shift;
  keys %$hash;
  my ($key, $value) = each %$hash;
  delete $hash->{$key};
  wantarray ? ($key, $value) : $key;
}

while (my $key = delete_first %hash)
{
  do_stuff();
}