The "key" is to push value/key pairs on to @holder. Consider:

use strict;
use warnings;
use Data::Dumper;

my $counter = 3;

my %hash = (
    a1_2 => 0.556,
    a1_3 => 0.345,
    a2_1 => 0.556,
    a2_3 => 0.125,
    a3_1 => 0.345,
    a3_2 => 0.125,
    );

for my $outer (1 .. $counter) {
    my @holder = ();

    for my $inner (1 .. $counter) {
        next if $outer == $inner;

        my $tracker = "a$outer\_$inner";

        foreach my $key (keys %hash) {
            next unless $key eq $tracker;

            my $value = $hash{$key};
            print "$tracker : $key : $value\n";
            push @holder, [$value, $key];
        }
    }

    my @holder_sorted = sort { $a->[0] <=> $b->[0] } @holder;
    print map {"$_->[1] => $_->[0]\n"} @holder_sorted;
}
[download]

Prints:

a1_2 : a1_2 : 0.556
a1_3 : a1_3 : 0.345
a1_3 => 0.345
a1_2 => 0.556
a2_1 : a2_1 : 0.556
a2_3 : a2_3 : 0.125
a2_3 => 0.125
a2_1 => 0.556
a3_1 : a3_1 : 0.345
a3_2 : a3_2 : 0.125
a3_2 => 0.125
a3_1 => 0.345
[download]