A AoH would be better than a HoA. You want to work with a list of people.

However, it's still possible to do what you want with the structure you have. What you need to do is sort the indexes.

my @sorted = sort { $person{firstname}[$a] cmp $person{firstname}[$b] 
+}
             0 .. $#{ $person{firstname} };

foreach (@sorted) {
   print("firstname: ", $person{firstname}[$_], "\n");
   print("lastname:  ", $person{lastname }[$_], "\n");
   print("city:      ", $person{city     }[$_], "\n");
   print("\n");
}
[download]

Or if you want to modify the structure itself,

my @sorted = sort { $person{firstname}[$a] cmp $person{firstname}[$b] 
+}
             0 .. $#{ $person{firstname} };

foreach (keys %person) {
   @{ $person{$_} } = @{ $person{$_} }[@sorted];
}

foreach (0 .. $#{ $person{firstname} }) {
   print("firstname: ", $person{firstname}[$_], "\n");
   print("lastname:  ", $person{lastname }[$_], "\n");
   print("city:      ", $person{city     }[$_], "\n");
   print("\n");
}
[download]

Notice how hard it is to extract the information you want? And how you have to assume the three arrays are of the same size? Those are indication that your data structure is poor.