This is a very tough AHC. The system is designed to drown a 3rd party before it can ever gain any traction. With that being said I suppose the only way to do it is:
Start off with an Al Gore victory like Plumber said.
9/11 happens and Al Gore launches the invasion of Afghanistan in 2001, just as in OTL
In OTL NM congressman Tom Udall was unopposed in 2002. In this scenario former NM Lt. Governor Roberto Mondragon (who won 10% in the 1994 governors race as a Green) runs against Udall and, with the support of both Republicans looking to "vote against The Democrat" and anti-war Dems, scores the upset.
Joe Lieberman convinces Gore to invade Iraq in 2003.
OTL San Fran mayoral race was a razor thin affair in which Gavin Newson edged Green Party candidate by 11,000 votes. 5,501 of these voters are so angry at the War on Terror they decide to take it out on Newsom. Matt Gonzalez wins the race 50.001 to 49.999
Bush (or Whoever) runs against Gore in 2004 under a promise to expand the war on terror to Iran and Syria.
Ralph Nader runs as a Green in 2004 and not a an independent.
Dennis Kucinich gives Gore a tough primary race. After losing in the primary he angers Democrats by running as VP candidate for Nader.
The Vermont Progressive Party becomes the Vermont Green Party in 2004, giving the Greens a handful of local state seats.
Nader wins say 5-7% of the votes in 2004. This performance, coupled with the one congressional seat, the mayors seat in San Fran, and a handful of local seats in Vermont, now have a foundation upon which to build on.
2008 the Dems nominate Hillary Cinton, much to the chagrin of the anti-war Dems who supported Obama. Se further alienates the anti-war Dems by picking Wes Clark as her running mate.
Dennis Kucinich wins the Green Party nomination and selects Roberto Mondragon as his running mate. Republicans score the win behind John McCain and Tim Pawlenty, but Cinton dos so poorly due to housing bubble collapse that Kuchinich's 8% is not a deal breaker and Dems don't blame the loss on Kucinich per say.
2012 Dems nominate Joe Liberman against McCain. He indicates it is time to expand war on terror to Iran. Anti war Dems are now in open revolt and dozens of elected Democrats publicly support the Mondragon-Matt Gonzalez ticket. Mondragon and Gonzalez also champion amnesty, something that allows the two Hispanics to make inroads with Latino population. In 2012 election they capture 10% of the total votes, mostly in NM and California.
Sorry, I can't do any electoral votes. I already stretched the limits of plausibility with that scenario above.