First of all, Dewey ran twice before for president just no way he's going to accept such a demotion as VP, so that's out of the queation. As for Earl Warren he was already Dewey's running mate in 48 -been there, done that. So that would leave Harold Strassen, jusr as good as any possibility.
Stassen might help hold the party together, but he and taft were not exactly friends. Leaving policies aside, I don't know if the conservatives ever quite forgave Stassen for challenging Taft in Ohio, while Stassen's delegates were influential in allowing Eisenhower to defeat taft at the convention on the first ballot (although fair play was probably more significant).
If Vandenberg had lived a few more years, he might have made Veep on the ticket. With him gone, not sure who the VP choice goes to. Dewey and Warren would not be terribly interested in the job (lots of bad blood there as well, especially between Dewey and Taft). I doubt that Stassen would accept, or even that he would get the offer. That depletes the upper ranks of candidates, meaning that the pick will probably be a lesser known candidate, maybe a favorite son. Unfortunatly, especially if taft picks one of his supporters, it's hard to be sure who it will be. Everett Dirkson would be a possibility, especially if he wants to reward his supporters, but that would do wonders for party unity. Otherwise, there are many possibilities. Some include:
Former Governor George Mickelson of South Dakota
Senator Wayne Morse of Oregon
Senator Leverett Staltonstall of Massachusetts
Senator Edward Martin of Pennsylvania
Former Governor Dwight Green of Illinois
Governor Alfred Driscoll of New Jersey
Senator Henry Cabot Lodge Jr. of Massachusetts
Senator Richard Nixon of California
These are by no means the only possibilities, and I make no claims about the likeliehood of any one of them being selected, but the politicians listed above (or many of them) had the party standing to be a worthwhile VP choice. However, it should be noted that Nixon and Lodge were included due to their role in the OTL election and ranking placement in the Eisenhower campaign, respectivly. In particular, this makes Lodge a hard sell as a potential VP, although Nixon, due to a mix of lack of prominence and anti-communist beliefs (not necessarily a plus for Taft) is not likely as well. As much as they are possible, there is also the possibility that they could be replaced with a similarly junior (in nixon's case in particular) favorite son or ideological placeholder. No clue who that would be, however.
Edit: Or they go back to default mode and pick a General. Namely MacArthur. The internal dynamics of a Taft/MacArthur on foreign policy will be interesting, and I don't see how such a ticket would be truly viable, but it is perhaps as likely or more as any domestic politician.