Who first coined the phrase "aviate, navigate, communicate"?
I don't know the genesis of the phrase, but I heard several WWII era military pilots interleave it with stories of their sorties, and of the debriefs for those sorties.  Based upon that, I would say that the expression dates back to at least the early-1940's.