My "algorithm" would be:
If all lines in the file are covered by CLA/SGA then add ASF header
Else if some lines in the file are covered by CLA/SGA then add ASF header and a note that some lines are not under ALv2.
Else If no lines are covered by CLA/SGA:
If you have reason to believe the contributor expected the file to be part of a BSD package, add BSD header
Else add a note that licensing is unknown and try to replace that file before graduation.
My 2 cents,
Bear in mind that the current code doesn't have a header; the situation here is to find a way to add a header so the licensing is clear. Once we add them, they shouldn't be moved per your comment, Alex.
Re: Justin's 'major changes happen' - it's for when a copyrightable change happens (authored by one of our committers). So more 'anything other than trivial' rather than 'major'.