The tricky part here is not pushing a section and its subsections down a level -- this just amounts to splicing in a couple extra "digits" on a set of these keys, and that's easy -- e.g.:

sub pushSection {
    my ( $hashref, @secNames ) = @_;
    my $base = (sort @secNames)[0];
    $baselen = length $base;
    my $newBgn = "AA";
    my $grex = join( '|', @secNames );
    @pushees = sort grep( /^($grex)/, keys %$hashref );
    foreach $i (0 .. $#pushees) {
        $_ = $pushees[$i];
        my $txt = $hashref->{$_};
        delete $hashref->{$_};
        s/^($grex)(.*)/$base$newBgn$2/;
        $hashref->{$_} = $txt;
        $newBgn++ if ( $i < @pushees && length($pushees[$i+1]) == $bas
+elen );
    }
}

chomp( @sections = <DATA> );
foreach (@sections) {
    next unless (/\S/); # not sure why I needed this
    $outline{$_} = "some text for section $_";
}
print "\nbefore:\n";
map {print "$_\t$outline{$_}\n"} sort keys %outline;

pushSection( \%outline, "AAAB", "AAAC" );

print "\nafter:\n";
map {print "$_\t$outline{$_}\n"} sort keys %outline;

__DATA__
AA
AAAA
AAAAAA
AAAB
AAAC
AAACAA
AAAD
AAAE
[download]

(There is one subtlety I'm missing there -- see below -- but there's nothing all that tough involved.)

The tricky part is providing the suitable method to determine what range of sibling-level sections should be included in this sort of push. E.g. in the example provided above, I'm pushing "AAAB" and "AAAC" down together, while the sibling sections around them ("AAAA" and "AAAD") stay where they are; "AAAD" should probably be "renamed" to "AAAC", etc. (this is the subtlety that I'm not covering yet):

#before :: after
AA      :: AA
AAAA    :: AAAA
AAAAAA  :: AAAAAA
AAAB    :: AAABAA  # need to insert "AAAB" above this line
AAAC    :: AAABAB
AAACAA  :: AAABABAA
AAAD    :: AAAD    # need to rename this to "AAAC"
AAAE    :: AAAE    # need to rename this to "AAAD"
[download]

But it's just as likely that on another occasion, starting with the same structure, the push would need to include AAAB, AAAC, and AAAD (and AAAE is now renamed to AAAC); and so on. Once you have a way of controlling (or discovering) the scope of a push, the actual mechanics of it won't be all that tough.

The part about "inserting" a parent node and "renaming" subsequent sections after a push has left fewer siblings "prior to" a given node is something I would tend to do as a "sanity pass" after the push -- go through the sorted set of section names at each level to look for gaps, and "decrement" subsequent names at the affected level to eliminate such gaps.

Update: fixed wording in last paragraph. Damn shame that decrementing strings is not so simple (thanks, jeffa)... but not surprising. What would be the "right" result for '$string--' when the initial value is "AA"? (Of course, this "shouldn't happen" in this sort of outline system, but it's the sort of detail that has to be dealt with.)