It seems that I was mistaken in my theory. Mark Millar himself answered this question for me at Millarworld.
Superman is in his early TWENTIES in the first book (he says so in captions in his opening scene) and Stalin dies here in the late fifties (after Sputnik went up as we see in the opening scene). My theory was that, since Superman is his bodyguard, he saved him from the first attempt on his life by poisoning.
Superman is in his 20s in book one, 40s in book two and 60s in book three, infant Kal being around 2 when rocketed to 1938.
I'm actually glad that I WAS mistaken this one time.