If Blair stood aside, it is not only possible but probable.
Brown would still win by a majority of over one hundred, given the myriad of issues surrounding Major and his government made a large Labour majority IMO a certainty. Major was beyond incompetent and events were rolling against him in a constant stream for years on end from Arms to Iraq, the Hamiltons, various sexual scandals(in a Government he himself stated was one of traditional family values and marriage whilst the hypocrite had cheated on his own wife) and major divisions over Europe which make any divisions in the Government today seem minor.(I mean to say, Major even went into a Party Political during the election on TV asking his own MPs not to tie his hands over Europe!)
There would not be the Tony Blair, Rockstar appeal, but Brown would have the tide of events in his favour, and I given this, I believe he would have won in 2001/02 as well. How he fares over the war on terror is anyones guess though.
How he has done IOTL is down to events I believe. Most of the programme he was for has been implemented so he cannot class himself as a great radical Prime Minister. I view him as a Lloyd George-type figure in this sense(the achievements of L-G were mainly whilst he was Chancellor and Asquith was in 10.Downing Street). In TTL, he would be able to implement much of his platform. A jibe was made against Major that he was in office but not in power. IOTL, Brown was in power but not in office.
If your looking for a Tory victory in '97 or a quick return to office shortly after, may I suggest Blair and Brown standing against each other with Prescott sneaking in by default.