Insertion in a file is not possible without copying the remaining part of a file. Your pseudo-code is the most "efficient" method in terms of operations.
What might help is writing the intermediate file to tmpfs to avoid writing twice to disk:
cat "$headerfile" "$infile" > /tmp/tmp
mv /tmp/tmp "$infile"
(change tmp
as needed if you want to run parallel commands).