Are all Japanese nationals who were born non-Japanese naturalized?

not naturalized: Renhō (DP, Tōkyō)

The term "natural-born" means someone who acquired that nationality by being born. It does not mean being born on the soil of the country you're a national of. For example, if one of your parents is a United States citizen, you will be born as a "natural-born" citizen of the United States as well, even if you were born in Japan (and not in a U.S. embassy or military base).

The opposite word for "natural-born" citizen is a "naturalized" citizen. In other words, you acquired that nationality not by being born into it, but by another means.

Unlike the United States and some other countries, Japan does not grant additional rights or privileges to those with natural-born citizenship; you can rise to the highest level of political office (prime minister) even if you're naturalized.

So does the above mean if somebody was born with Taiwanese citizenship with a Taiwanese passport, but then gets Japanese nationality as a teenager, then they must have acquired it through naturalization?

Not necessarily.

The reason for this is due to a massive change in the Japanese nationality law in 1985. Prior to 1985, the Japanese nationality law only gave natural-born citizenship to babies whose fathers were Japanese nationals (regardless of race, and regardless of where in the world you are born). If your father was not a Japanese national, then you would not be born as a Japanese. Even if your mother was a Japanese national.

After 1985, they changed the Japanese nationality law so that if either your father or mother was a Japanese national (again, regardless of race, and regardless of where you were born), you would be born as a Japanese national.

Instead of having a notation for 帰化 {kika} (naturalization) in one's 戸籍 {koseki} (Japanese national family unit register), people that obtain nationality this way instead have an entry titled 国籍取得 {kokuseki shutoku} (nationality acquisition) in the 身分事項 {mibun jikō} (personal matters) section. Another difference is that those who obtain nationality this way are not listed in the 官報 {kampō} (Japanese government Official Gazette) like those who naturalize are — as required by the Japanese Nationality Law.

One thing they did not make retroactive with the 1985 law was the 国籍選択 {kokuseki sentaku} (Nationality Choice) law, which says that Japanese who involuntarily acquire (through birth, marriage, or other means) foreign nationalities must officially declare their choice of nationality within two (2) years — which means most Japanese born as dual nationals must choose by the age of 22 as the official age of majority (a legal adult) in Japan is twenty (20) years old.

What this did was allow a lot of people, who were living in Japan with foreign nationality, to turn into Japanese nationals. Because these people did not apply for permission for citizenship the same way you do with naturalization and they inherited their nationality from their mother, they became de facto "natural born" Japanese nationals after-the-fact.

A famous example of this is 村田蓮舫 {MURATA Renhō}, a politician who uses the mononym 蓮舫 {Renhō} in public in her roles as a former model, then broadcaster, and now a serving politician. Born 謝蓮舫 {ㄒㄧㄝˋ ㄌㄧㄢˊ ㄈㄤˇ} (HSIEH Lien-fang / XIÈ Lián-făng) in 1967 to a Taiwanese father and Japanese mother, she was a natural-born citizen of the ROC. When the Japanese nationality law changed in 1985, the fact that she was born from a mother with Japanese citizenship meant she could suddenly become a Japanese national, without naturalizing, while a minor in Japan at the age of eighteen (18).

Now a mother, she has two twin children who are natural born Japanese.

蓮舫 {Renhō} is a Japan Diet politician (国会議員 {kokkai giin}) in the House of Councillors (参議院 {sangiin}). As she was re-elected in 2010 and Councillors serve six (6) year terms, won't have to campaign again until 2016.