Re Q1: If you give a small sample of relevant data in the hash structure, how you would like the sorting to come out, and a snippet of the code you've tried, help would come more easily. As it is, I'm not sure what you mean -- "sorting numerically on the internal keys" could mean different things, depending on the data and what you really want.

Q2: you want a regex substitution, like  s/^(\d)/chr(ord($1)+0x10))/e

Q3:

my @sorted_keys = 
   map { s/_0*//; $_ }
   sort
   map { s/(\d+)/sprintf("_%08d",$1)/e; $_ } keys %hash
[download]

(that's the Schwartzian Transform approach, which might be more efficient, whereas the method that Grandfather suggested is easier to grasp)