If Bill Clinton got into a scandal earlier, could he have lost the election in 1996? How could Bob Dole win that election?
It depends up in what kind of scandal. If it were a sex scandal, then as the whole Lewinsky affair showed the public actually rallied behind Clinton when he came under attack from the GOP. In fact his approval rating was 73% after the impeachment.
In order for a scandal to take down Clinton, it would have to be a Watergate/Iran-Contra type of affair where the President deliberately broke federal law and violated his oath to the Constitution. Even then, the scandal would have to break out every quickly in order for Clinton to lose - Nixon won in 1972 after the Watergate break in.
My general point here is that Clinton was hard to beat in 1996. Not because he was extremely popular at this time (he wasn't), but he's called "Slick Willie" for a reason. It's difficult to attack him and make it stick because he was great at pivoting and deflecting in order to survive politically. Also he was great at positioning himself as a positive contrast with Gingrich and the right wing Congress. The only Republican who lead Clinton in public polling was Colin Powell, but since the thread calls for a Dole Presidency I will try to make this work:
Somehow, Dole beats Clinton and on January 20, 1997 he is inaugurated as the nation's 43rd President. Dole would slash taxes and cut federal spending. He would probably intervene in Kosovo. If he runs in 2000, his age would be an issue but I expect he is reelected on the good economy. 9/11 would probably still happen, but it's possible that Dole's response would be more level-headed than Bush's. (So perhaps a less wide reaching Patriot Act closer to what Orin Hatch originally proposed). Afghanistan is invaded, there might still be an Iraq intervention but with Dole it could be less likely. The GOP wins in 2004, but come 2008 Iraq is a mess and the economy crashes on schedule.