Unlike most, I happen to think Gingrich would perform better against Clinton that Dole. It's easy to forget that Dole only lost by 8 pts (49-41-8%), and was a completely inept campaigner (I mean, c'mon, falling off a barnstorming stage??). Gingrich, as polarizing as he was, is much more charismatic than Dole, and probably, much more willing to draw a stark contrast from Clinton than Dole.
Having said that, I Clinton still wins by healthy margin. The growing '96 economy would still be too much to overcome.
Clinton - 352 (-27)
Gingrich - 186 (+27)
Clinton wins 48-41-9%