Semi-answering my own question: I don't see any usage of "JFK" in NewspaperArchive.com prior to August 1960. The earliest newspaper reference I've found is from the San Antonio Express of 1960-08-18, "GOP, Demos Trade Gags":
... In Dallas, the Texas Democratic Committee came up with a battle slogan of its own: a "Frontier License" that reads "4-JFK-LBJ" All The Way. The license was unveiled by Chairman J.E. (Ed) Connally [No, the one you're thinking of was John B. Connally; this one was the husband of Virginia Boyd Connally, first female physician in Abilene] ...
By 1960-12-08, the Tucson Daily Citizen could write the headline "JFK Will Take Reins In Hands."
There's also these interesting items:
(Tucson Daily Citizen, 1960-12-12)
MONIKER TROUBLES — American newspapers are in something of a stew. What will headline writers call our next president?
In a dispatch sent to telegraph editors by the United Press International, the whole business is given quite an airing.
Suggests a California editor, "If we can call Eisenhower Ike, don't see why we can't call Kennedy Jack. Would prefer it to JFK because of LBJ. Or how about 'Fitz'?"
The dean of a school of journalism has this to say: "If I may toss in my unsolicited nickel's worth, let me register a hearty vote in favor of JFK if initials or abbreviations of some kind must be used to designate the President of the United States in headlines. I have seen Jack a few times and I think it is in bad taste. I hope it doesn't catch on."
A Pennsylvania editor says, "We're going to go along with JFK whenever we find it impossible to use the full name 'Kennedy.'"
Finally then, this from a Massachusetts newsman: "In relation to all the childish comment on what to call Kennedy—JFK, Jack, or Kennedy—just don't call him 'Mr. K.' If Ike was acceptable, then who is Jack that we should give him the falsities of British royalty in a world that needs more personal touch than ever!"
Or how about the Kid?
(Nome Nugget, 1961-01-04)
DON'T CALL ME "JACK" — Palm Beach, Fla. (AP) — President-elect John F. Kennedy wishes newspapers would stop referring to him as "Jack" in headlines.
But he has no objection to use his initials, JFK.
Kennedy wants it understood, however, that he is making no strong protest about the "Jack" headlines. It's just that he feels they aren't in keeping with the dignity of office of the President.
It was brought up by a reporter who asked the Press Secretary, Pierre Salinger, how Kennedy feels about headlines referring to him.
So it seems at first glance that the term "JFK" was invented only by necessity, after Election Day 1960; before that, he was just "Kennedy."