You might try something like this:

#!/usr/bin/perl
use strict;  
use warnings;  

my $master = 'master.txt';
my $newmaster = 'master.tmp';
my $update = 'update.txt';

open my $updatefh, '<', $update or die "$update: $!";

my %updates;
my @updates;
foreach my $line (<$updatefh>) {
    my $key = substr($line,3,12);
    $updates{$key} = $line;
    push(@updates, $key);
}
close($updatefh);

open my $masterfh, '<', $master or die "$master: $!";
open my $newmasterfh, '>', $newmaster or die "$newmaster: $!";

foreach my $line (<$masterfh>) {
    my $key = substr($line,3,12);
    if(exists($updates{$key})) {
        print $newmasterfh $updates{$key};
        delete($updates{$key});
    } else {
        print $newmasterfh $line;
    }
}
close($masterfh);

foreach my $key (@updates) {
    if(exists($updates{$key})) {
        print $newmasterfh $updates{$key};
    }
}
close($newmasterfh);
[download]

This assumes that each key appears only once in master.txt. Some change would be required if you want a single line in the update file to update multiple lines in the master file.

This also assumes the update file is small enough that the hash of updates fits in memory but will work even if the master file is larger than available memory.

The order of lines in the master file is maintained. Any new lines added from the updates file are appended in the same order as they appeared in the updates file.