How can a newspaper prove that the block wasn't generated prior to the publish date? If I were to hash the headlines from a 1969 "ON THE MOON!" article, would it prove that my block is older that the bitcoin's genesis block?
You have to predict exactly what the headline is going to be though "On the Moon" is a fair guess but the chances you would get "Men walk on the moon" (plus "astronauts land on plain; collect rocks, plant flag" if we're using the subheadline too) exactly correct to fake it are really low. That's only possible on a very small number of dates where there's a known huge event coming up.
That would only prove your block is NOT from before 1969. The date of the article in question is 03/Jan/2009. Which is around the time of the block itself (thus proving the block wasn't generated before 2009).