fast, flexible, stable sort gives a good way of sorting strings in the way that you want. That reduces this to being a problem of producing the list to sort.

Try this:

my @list = map {my $first = $_; map {"$first|$_"} keys %{$myhash{$firs
+t}}} keys %myhash;
sub XFORM {
    # Extract the sort key from $_[0] and return it.
    # This will often be written in-line
    # rather than as a real subroutine.
}
my @sorted= @list[
    map { unpack "N", substr($_,-4) }
    sort
    map { XFORM($list[$_]) . pack "N", $_ }
    0..$#list
];
foreach my $key (@sorted) {
  my ($first, $second) = split /\|/, $key;
  print "$first: $second: $myhash{$first}{$second}{'one'}\n";
}
[download]

(Untested code...)