He probably replaces Barkley, who at this point was quite old. Eisenhower might've taken the VP slot, but probably not. My guess is it would have been Kefauver. Or, Gen. Ridgway.
Taft is probably the Republican nominee. He loses.
(Slight chance of MacArthur being the nominee, but I sort of doubt it).
Stevenson/Johnson is not a bad guess in '56... although I rather think it's Harriman/Johnson. The McCarthyites, however, have not imploded as they have in OTL, because they have taken on the stronger role of critic of the Democratic administration, rather than the far right extreme of the more moderate centrist Republican party. So it's very possible we could see a McCarthyite, maybe even McCarthy himself, or Knowland, nominated on the GOP side.
Of course, it could be a more moderate candidate, depending on how badly they lost with Taft. Possibilities: Lodge, Stassen, Warren. Probably Warren (biggest state).
One immediate interesting possibility: It is suspected that one of the strongest reasons Lodge lost to Kennedy in the 52 Senate race is because Lodge was Eisenhower's campaign manager. Take away that distraction, and Lodge might win... butterflying away JFK at least in the immediate term.