If you can live with a hashref rather than a hash at the top level...

use List::Util qw[ reduce ];

my $line = 'a1:a2:a3=key';
my $href = reduce{ my $r={}; $r->{$b}=$a; $r } reverse split /:|=/, $l
+ine;
print Dumper $href;
$VAR1 = {
          'a1' => {
                    'a2' => {
                              'a3' => 'key'
                            }
                  }
        };
[download]

Update: It struck me later that hash refs are a distinct advantage as it avoids the collision problem graff brought up.

#! perl -slw
use strict;
use List::Util qw[ reduce ];
use Data::Dumper;

my @AoH;
while( <DATA> ) {
    chomp;
    push @AoH,  reduce{ 
        my $r={}; $r->{$b}=$a; $r;
    } reverse split /:|=/, $_;
}

print Dumper \@AoH;

__DATA__
a1:a2:a3=key1
a1:a2=key2
b1:b2:b3:b4:b5:b6:b7:b8:b9=key3
[download]