Prepend to Very Large File in Fixed Time or Very Fast

I have a file that is very large (>500GB) that I want to prepend with a relatively small header (<20KB). Doing commands such as:

cat header bigfile > tmp
mv tmp bigfile

or similar commands (e.g., with sed) are very slow.

What is the fastest method of writing a header to the beginning of an existing large file? I am looking for a solution that can run under CentOS 7.2. It is okay to install packages from CentOS install or updates repo, EPEL, or RPMForge.

It would be great if some method exists that doesn't involve relocating or copying the large amount of data in the bigfile. That is, I'm hoping for a solution that can operate in fixed time for a given header file regardless of the size of the bigfile. If that is too much to ask for, then I'm just asking for the fastest method.