Henry Cabot Lodge seems like the best choice. He was already on a national ticket in 1960, so it's within the plane of reason. And he won three primaries in 1964 by write-in without leaving Vietnam.
Give him the win over JFK in 1952 and you might have a deal.
Alternately, you could use his son, George Lodge, who was defeated by Ted Kennedy in 1962. I'm not sure what could put him on a national stage as early as 1968, however, maybe he could have won Kennedy's seat in 1958 if, for some reason, JFK got into trouble.