I suspect any one-liner is going to be somewhat unwieldy. Here's one using Tie::File:

ken@ganymede: ~/tmp
$ cat > pm_add_header_1
HEADER
XXXXX
YYYYY
ZZZZZ
ken@ganymede: ~/tmp
$ cat > pm_add_header_2
AAAAA
BBBBB
CCCCC
DDDDD
ken@ganymede: ~/tmp
$ perl -Mstrict -Mwarnings -MTie::File -e 'my @f; my $i = 0; tie @{$f[
+$i++]}, q{Tie::File}, $_ or die $! for @ARGV; unshift @{$f[1]}, $f[0]
+[0];' pm_add_header_1 pm_add_header_2
ken@ganymede: ~/tmp
$ cat pm_add_header_2
HEADER
AAAAA
BBBBB
CCCCC
DDDDD
ken@ganymede: ~/tmp
$
[download]