In addition to the legal arguments, it would be damn near politically impossible to argue that John McCain, the son of a naval officer born while his father was stationed overseas in the service of his country, is somehow Constitutionally less worthy than someone born on U.S. soil. I would expect that any judge would interepret any ambiguity to permit the Presidency to go to a military dependent born on an overseas station.
Not a US citizen. Embassies are part of the host nation.
Don’t know about this.
This seems to come up every few months on the SDMB, a little different every time. A related thread: Will the Constitution be amended so Schwarzenegger can be president? - Great Debates - Straight Dope Message Board
Both the current U.S. secretaries of Labor and of Commerce were born overseas (in Taiwan and Cuba, respectively) and are thus ineligible to serve as President.
Chester Arthur’s foes alleged that he was actually born on Canadian soil and not in northernmost Vermont, but most historians think that’s bunk. Herbert Hoover had spent so much time doing hunger-relief work after WWI that some suggested he wasn’t eligible to serve as President, as he had not “been fourteen years a resident within the United States” (Art. II, Sec. 1, cl. 5). Nothing came of it, though. Why penalize a guy who’s doing humanitarian work?
A slight tangent: When Dick Cheney was selected as George W. Bush’s running mate in 2000, it was noted that he was a tax-paying and voting resident of Texas, as was Bush, obviously. That would probably mean that the Bush-Cheney ticket would have had to give up Texas’s Electoral College votes, since the electors from the state would be choosing a President and a Vice President, “one of whom, at least, shall not be an inhabitant of the same state with themselves…” (Amendment XII). Cheney rediscovered his Wyoming roots in a hurry, a lawsuit over the issue was dismissed, and the rest is history. I hear he still goes back to hunt in Texas now and then, though. 
I personally would have no problem amending the Constitution so that a naturalized citizen - perhaps with an even longer residency requirement? - would be eligible to serve as President. It’s certainly politically fraught, though.