Suppose I have an already existing codebase which does not have any license headers in any of the source files, nor does it have COPYING file.
So when I add all the neccessary GPL “cruft” to, say, revision 1000, will all previous revisions be GPLed as well or do I need to rewrite my repository history to include GPL license from the revision 0?
4
No – the GPL license controls how the code is to be distributed, it isn’t an intrinisic property of the code. Code doesn’t become GPL – it is distributed under the GPL
If you aren’t distributing the earlier versions of the code then the license has nothing to do with it.
The default status for copyright in most countries is “all rights reserved”. So, any previous distribution of the code by yourself did not grant the receipients the right to modify or distribute the code.
Adding cruft to each source file isn’t necessary; it’s just common practice.