I don't think the Dems' loss in '56 would be substantially worse than it was IOTL: a relatively young photogenic VP candidate would mitigate any lingering religion-based concerns to a large extent. But I digress.
What you outlined sounds to me like a tailor-made formula for a long, nasty, potentially deadlocked Dem convention in 1960. I could see Kennedy and Humphrey forming a loose stop-Johnson alliance, while Johnson called in every IOU, twisted every arm, etc. to get the necessary votes. In that case, Humphrey would have to go, essentially hat in hand, to Joe Kennedy and convince him that he, Humphrey, is the only candidate that could mean a Dem victory (the implication being that Johnson would be a hard pill to swallow in the north). He might have to go to the length of promising the old man a substantial cabinet post for his son: say, Attorney General. In turn that would carry the promise of a Kennedy candidacy in 1968, when Kennedy would be only 51--still relatively young.
Of course, even if all this plays out as described, Humphrey would have to scramble against Nixon. big time. True, there wouldn't be the religious factor but Nixon had the gravitas of eight years in the second office for openers. Add to that the way he was known to be able to handle Khrushchev and you have a substantial GOP advantage.
I'd suggest further that the debates--if they occurred--would be about a wash on TV. Humphrey's rapid-fire, almost nervous style would balance Nixon's somewhat grim appearance. Drop out that factor and those that listened on the radio might tilt the balance to a degree--and in OTL radio listeners judged Nixon the better of the two.
Long story short: going to be tough to get Humphrey in the White House in 1960.