A few tidbits for thought:
* In 1962, Arthur Schlesinger released a historical ranking of the Presidents (the first of its kind since 1948). Dwight Eisenhower came in at 21st, tied with Chester Arthur, below Herbert Hoover (19) and Benjamin Harrison (20) and just ahead of Andrew Johnson (22) and Zachary Taylor (23).
* Allan Lichtman's Thirteen Keys to the White House gave nine (!!!) negative keys towards the incumbent (Republican) party going into the 1960 election, including recession, no policy change, and the perception of a foreign military failure. To be honest, that foreign military failure key seems a bit debatable to me. I think it was the U-2 spy plane being shot down and the escalation of the Cold War. Since 1860, the only other election to have that many negative keys against the incumbent party was 1876. To contrast, Eisenhower's 1956 reelection campaign only had one negative key, the fewest of any election save for 1904.
Dwight Eisenhower may be a venerable figure today but by 1960 the country was ready for a change.
I'll go one step farther: I think Richard Nixon is just about the worst candidate for 1960 because it requires him to do something he's basically incapable of doing: run a positive campaign. Sitting Vice Presidents generally do a terrible job running for President because they have to establish themselves as their own man while singing the praises of their President and portraying their opponent as dangerous. There's a reason George H.W. Bush did it and Richard Nixon couldn't. By 1988, the Cold War was ending. By 1960, the perception was that it was out of control, and that took the best tool that Richard Nixon had out of his tool box. Richard Nixon was a brilliant Red Baiter. His best campaigns were 1946 an 1950, running against a perceived corrupt Democratic establishment. How do any of those tools help him in 1960 where he had to be the candidate for a different establishment, let alone a different establishment that was perceived as being weak on Communism?
The best thing Richard Nixon had going for him was that Barry Goldwater didn't run and the GOP did not have a protracted nomination contest. The party was generally aligned behind Nixon.
All of which to say, I don't think any Republican save for Eisenhower could have won.
What does John F. Kennedy's Vice Presidential selection mean?
Jack being chosen as VP drops Bobby in the middle of Stevenson's campaign, and Bobby is going to annoy the living shit out of everybody on board. Stevenson's high-mindedness and Bobby's real politik aren't going to mix at all, despite the fact that Bobby is going to be right about everything.
It's easy to envision a scenario where Adlai Stevenson spends more time running against his own running mate(s) than Ike, which will produce one of two scenarios: it'll make Stevenson so annoyed at the two of them that he runs a more aggressive campaign in 1960 or he says "Fuck this, I'm done." and stays out of 1960.
Either way, if John F. Kennedy is chosen as Stevenson's running mate in 1956, it's unlikely to be harmonious behind the scenes and it's very possible that it lights up a warning flare within the Democratic establishment of how they do business and everyone is just a little more prepared for the Kennedy's in 1960.
Maybe a Johnson/Humphrey ticket in 1960?