In 1955/56 Joe Kennedy tried to convince LBJ to seek the Democratic Nomination, a campaign which he would support financially and w/ backroom deals, if Johnson would choose JFK as a running mate. Joe figured Johnson could do well without winning, which would bolster JFK's chances at the nomination in 1960. What would have happened if Johnson, not Adlai Stevenson, faced Eisenhower in '56? I assume they would've done far better but could they have one?
There's no way they could have won; Eisenhower was nearly unbeatable (even after two heart attacks and a bout of stomach disorder). If Ike wants the Presidency, he's got it. Should he decide not to run, however, that would throw the entire thing open.
Another problem is Johnson, himself. LBJ did make an effort to get the nomination in '56, but it was a late affair, and not a well run run (a pattern that would be repeated in the first months of the '60 campaign). In '56, part of the problem is simply that Johnson wanted to be President, and I don't think he saw any real chance of winning in '56; and there was no way in hell he was going to sacrifice his ambitions to help some young, snobbish blueblood (it didn't help that LBJ formed a very negative option of JFK when they served together in the Senate; finding the young man to be little more than a playboy who'd daddy had bought him a Senate seat).
Now, assuming the stars align: Ike decides not to run, and an the Republicans nominate Richard Nixon (or, if you really want to screw it up, someone like Bill Knowland. Nixon's power within the party was not strong at this time, and there were efforts to get to drop him from the VP spot as it was. Getting his arch-enemy, Bill Knowland, to run in 56 wouldn't be that far out of the question). This throws the electin right open, and the Democrats now feel they have a real chance.
Even if LBJ decides to run in this case, he's going to have some real problems. First of all, he is going to need the support of Liberals to win, and, in 1956, Johnson had done almost nothing to be able to win them over (his Civil Rights bill wouldn't be passed for another year, and even that barely made a dent in his reputation as a Southern Conservative). Secondly, is Johnson's own personality. He is someone who wanted the Presidency so bad, that he often 'locked-up' when making the run due to the fact that he was terrified of failing at his life's ambition.
Truthfully, in the case of a No-Ike in '56 timeline, I think that Estes Kaufver would be the most likely Democratic nominee. Kaufver might well choose Kennedy, mind you, and might actually stand a chance of winning.