Given his age and inexperience, the pick would likely be someone who older with a greater resume for balance yet, as with all VPs, won't overshadow him.
Former Congressman and the current Secretary of the Interior Stewart Udall would be a good choice for geographical purposes being from Arizona as was the Republican Presidential nominee Barry Goldwater.
Abraham Ribicoff, a then current Senator of Connecticut, former governor, and former H.E.W. Secretary, would have been an historic choice because of his religion although two New Englanders might have been considered a no-go.
Also from the US Senate Alan Bible (NV) or Al Gore (TN) would probably fit the bill.
A plethora of US Representatives such as Eugene Keogh (NY) would do the trick although selecting a woman like Leonor Sullivan (MO) or Martha Griffiths (MI) would have been groundbreaking.
UN Ambassador Adlai Stevenson II (whom RFK did not vote for in 1956).
W. Averell Harriman ticks a lot of boxes.
John Connally would have been a wild if morbid selection. His experience was at that point even less than RFK's but it would have been a bone tossed to LBJ.