The physical location of where you were born doesn't matter. It's if your parents are American citizens, in which case you would become one. People living in territories are American citizens too, so if your parents lived there it would be valid.
Interestingly, Barry Goldwater was not born in a state. He was born in Arizona Territory, 3 years before it became a state.
No, that is not true. Native-born means that you have to have been born on native soil. Territories count since they are American territory, but if you were born in say, India, you cannot be President.
Actually the term is "natural-born" citizen. If your parents were US citizens living abroad, your still natural-born.
Besides that, anyone who thinks there would be something wrong with someone born to US citizens living abroad being president is a f'ucking idiot.