Well, he would need to avoid the car crash in '65 that put him in a wheelchair for one. He would also probably have to win the governorship in '62 which he lost. So, it's hard, but not impossible. The real question is, could he beat Johnson?
Romney ran a horrible campaign, so Nixon would do better. However Johnson would still get the Upper South (the Deep South is Dixiecrat territory) at that point, negating Romney's advantage in the Midwest. Nixon might balance this out by doing better in the West and possibly in the South, though the South didn't start becoming the swing area it is today presidentially until the late '70s.