Yet another way is to cheese together a tied filehandle that simply prepends whatever you write onto the beginning of the file. Kinda like what you're doing, but with a simpler interface.

package Beginning;
use Fcntl;
sub TIEHANDLE {
        my($class)=@_;
        return bless { fh=> undef }, $class;
}
sub OPEN {
        my($self)=shift;
        return sysopen($self->{fh}, $_[0], O_RDWR | 
             O_CREAT, 0666);
}
sub CLOSE {
        close($_[0]->{fh}) if ($_[0]->{fh});
        $_[0]->{fh}=undef;
}
sub PRINT {
        my($self,$len)=shift;
        local $/;
        $_=$self->{fh};
        seek $_, 0, 0 or warn "$!";
        my $buf=<$_>;
        seek $_, 0, 0 or warn "$!";
        print $_  @_;
        print $_ $buf;
}
[download]

Then to use it just:

tie *FH, "Beginning";
open(FH, "Hello");  # This will actually be read/write
print FH "Look ma, I'm first", scalar(localtime), "\n";
close(FH);
[download]

It's incomplete and not scalable, just something to think about. A fun modification might be to have the PRINT callback "shuffle" the blocks of the file forward with each write. This would save wear-and-tear on $buf (but not your disk!).