In 1998, Clinton is impeached as OTL. He launches Desert Fox as OTL...then a Republican on the judiciary committee remembers Hussein Kamil's interview. A new charge is brought, but as the others, it fails in the senate.
Impeaching Clinton over Iraq divides the Republican Party. While Bush earns the nomination as OTL, he loses support from a number of "Taftite*" Republicans and does not come close to a majority in Florida. Gore is sworn in. 9/11 happens. Republicans make gains in 2002, increasing their majority.
McCain easily defeats Gore in 2004, thanks to swing voters. McCain launches his "Rogue State Rollback" plan by launching an invasion of Iraq, using Hussein's support for terrorists as the pretext for war. The invasion succeeds, though the insurgency begins as a result and goes much as OTL. Democrats gain House and Senate in 2006. In 2008, the McCain administration launches an airstrike on the Roki Tunnel in South Ossetia and provides US air support for the Georgian forces. Between Russian air and air defense forces being deployed to the Caucasus (resulting in the loss of several US aircraft), and backlash from the US siding with Georgia (after reports confirm that the Georgian Government ordered the attacks on South Ossetia that started the whole thing), the US mission in Georgia becomes extremely controversial. As a result, McCain (and Lindsey Graham, his VP), loses to Obama/Biden.
Obama/Biden face opposition from Republicans from the beginning, but one of the most significant is the operation in Libya. While the interventionist Republicans praise Obama (or criticize him for not intervening sooner), the Taftites, joined by a few "Wallaceite**" Democrats like Dennis Kucinich, Paul Wellstone and Cindy Sheehan call for Obama's impeachment for violating the War Powers Act and lying to Congress. Impeachment fails, but the damage is done. Aided by Ron Paul's endorsement and internet support, Johnson narrowly ekes out a win in the primaries over Romney and Santorum.
* A term of my invention based on the term below. Named, of course for Robert Taft, "Mr. Republican".
** A term coined by the New Republic's Peter Beinart, to attack those who did not support his foreign policy views. (Ironically he was attacking the predecessor as TNR editor, Henry Agard Wallace.)
http://www.tnr.com/article/politics/fighting-faith