This is a first short hack. I hope this helps you:

#!/usr/bin/perl

use warnings;
use strict;

my %hoh = (
    "A1" => { "bl" => 0, "ff" => 4, "gg" => 3 },
    "A2" => { "cc" => 5, "dd" => 4, "ee" => 9 },
    "B1" => { "og" => 0, "wo" => 4, "ee" => 3 },
    "B2" => { "oo" => 5, "pp" => 4, "zz" => 9 }
);

# The names of the hashes to print
my @keys_to_sort = sort keys %hoh;

# As long we still have hashes to print
while ( @keys_to_sort ) {
    # Extract hashes to use in current row
    # Smarter way to get the first part of the hash name?
    my $last = substr $keys_to_sort[0], 0, 1;
    my @keys_to_use;
    for ( my $i = 0; $i < @keys_to_sort; $i++ ) {
        if ( $keys_to_sort[$i] =~ /^$last/ ) {
            push @keys_to_use, splice( @keys_to_sort, $i, 1 );
            $i--;
        }
    }

    print "\n", join( "\t", @keys_to_use ), "\n";
    # Print key number $i of every hash in the array
    # Exchange keys %... with maximum number of keys in @keys_to_use
    for ( my $i = 0; $i < keys %{$hoh{$keys_to_use[0]}}; $i++ ) {
        # Print hashes - This relies on all hashes having
        # the same number of keys
        print join( "\t", map {
            my @keys_of_hash = sort keys %{$hoh{$_}};
            $keys_of_hash[$i] . "=>" . $hoh{$_}{$keys_of_hash[$i]};
        } @keys_to_use ), "\n";
    }
}
[download]

I get this as output:

A1      A2
bl=>0   cc=>5
ff=>4   dd=>4
gg=>3   ee=>9

B1      B2
ee=>3   oo=>5
og=>0   pp=>4
wo=>4   zz=>9
[download]

As said in the program, this piece of code relies on every hash to have the same number of keys and that the keys remain the same while looping over them. This could be improved by replacing keys %{$hoh{$keys_to_use[0]}} with a function that determines the maximum of keys.

I think here are some more flaws in it, but I hope that I could help you.