Were there any interactions with China prior to the European colonial powers or Ming?

The first interactions that may have been recorded were during the Three Kingdoms period, where expeditionary forces of the Kingdom of Wu may have landed on the island during a series of expeditions which also reached Japan. Later, there was extremely limited trade with the aborigines throughout the Song Dynasty.

When did the first Hakka, Fujianese or other settlers arrive in Taiwan?

Major Chinese settlement did not start until after the Dutch establishment of Fort Zeelandia in 1624. They primarily arrived for economic opportunities and due to Dutch encouragement.

When and in what capacity did the Ming Dynasty interact with Taiwan - why did they decide to take it?

Admiral Koxinga of the Ming Dynasty was in the midst of a losing civil war with the Qing Dynasty. In order to secure a power base safe from the Qing, he led Ming Dynasty troops to capture Taiwan to use as a naval base to harass the Qing, and later, as a bastion of resistance. His plan was to use Taiwan to perhaps invade the Spanish Philippines, and from there to build up military and economic strength to restore the Ming Dynasty, although with the death of the last Ming Emperor this may have been less feasible.

How did the Qing Emperors feel about Taiwan? Did the average late 17th-19th century Chinese feel that Taiwan was part of the Chinese Empire?

While initially Koxinga defeated Qing expeditions to capture the island, after his death from Malaria his son agreed to pledge fidelity to the Qing in return for security: however the Qing were later able to capture the island.

When did the modern mythology that "Taiwan has always been a part of China" become a part of mainstream history?

This is a leading question as it is highly political. I'm not sure if I can answer this fairly, but the prevailing narrative around 1950 was that the KMT forces were the legitimate government of all China that just happened to mainly be in Taiwan at the time. In a sense, the thinking was "China belongs to Taiwan." With worldwide recognition of the PRC around 1970 as being the legitimate government of China, the prevailing PRC position is precisely that, but the other way around. Taiwanese independence first started around 1895 with the declaration of the Republic of Formosa, but this was a reaction to the Qing Dynasty's defeat by Japan in the first Sino-Japanese War.

Here's a blog column that tries to provide historical references to show that Taiwan does not belong to China. It is biased, but there may be some history snippets worth investigating.

http://mypaper.pchome.com.tw/hintaiwan/post/1320447962
The column is literally named "Taiwan never belonged to China - what the textbooks don't teach".

For those who don't read Mandarin, here's a rough summary of a few posts from the blog column.

One

In 1683, Qing defeated the Kingdom of Tungning, but they waited for 8 months before claiming Taiwan, because they were debating whether to even keep Taiwan. The author then deducts that this means Taiwan was "new" to them, otherwise it would be obvious they would immediately "reclaim" Taiwan. Kangxi (1662-1722) was against claiming Taiwan, quoted to say that "Taiwan is overseas land, not realted (to us), and had never received our influence", also that "Taiwan is a small plot of land, nothing to gain, nothing to lose" and "little plot overseas, not worthy of China".

Two

Yongzheng (1678-1735) was quoted to say "Taiwan was never part of China, our emperor decided to claim it".

Three

In 1662 when Koxinga prepared to attack Taiwan (occupied by the Dutch at that time), he announced that "I swear to reclaim the homeland, but the isolated islands (meaning Kinmen Islands etc where he was based at that time) bear hardship so I have decided to take the risks and conquer the unconquered. We shall gain strength and wait for the prime opportunity; I am not running overseas for run away from the fight."

The author claims that Koxinga obviously views Taiwan as foreign and overseas land, not Chinese (Ming/Qing) territory.

Four

In the 17th century, Ming fought with the Dutch when they occupied Pengu Islands for the second time. In the peace treaty that followed, Ming demanded that the Dutch leave Pengu, but had no problem with them occupying Taiwan. Hence the Dutch set up their base at the now Tainan region, establishing Taiwan's first ruling administration.

The author claims that this is evidence that Ming never thought of Taiwan as Chinese territory.

Five

Also in Book of Sui (636 AD), it states that the Sui dynasty once "invaded" Taiwan and returned with people and goods, then no further mentions. The author claims that if Taiwan had been Chinese territory, they wouldn't have viewed it as an "invasion", and there would have been further mentions.

The author also points out that many people like to mention the fact that Emperor Yang sent troops to Taiwan, claiming that this proves China had claimed Taiwan. But the original text not only stated that "Taiwan did not obey and resisted our troops", and it stated that they "kidnapped 1" as well as "raided all the cloths and armor and returned", plus other statements of raiding and pillaging, as well as references that "it ended then", meaning Taiwan was not claimed.

Six

In the History of Ming edited by the Qing dynasty, Taiwan was classified under "Stories of Foreign Countries", listed among Japan, Korea, etc.

Seven

In 1603 when Ming sent General Shen to Taiwan to eradicate the pirates, a conversation was recorded in "舟師客問" when someone asked the general, "the pirates live in Taiwan, not in our country (so why go fight them)". The general was quoted to answer: "indeed the pirates occupy not our land, but if we use this as an excuse to not send troops, then there will never be a day when pirates are defeated".

Eight

After General Shen returned to Ming, Chen Di who went on the trip wrote the famous "東番記", one of the earlier articles on Taiwan. After the article was written, a Ming scholar then wrote an response saying "if not for General Shen's victories, we would not even know about the existence of Taiwan".

Nine

The "臺海使槎錄" mentions that "Taiwan first became Qing territory in 1683, it sit far out in the seas, and officials did not keep proper records, giving no official records on how the Qing Dynasty ruled over Taiwan in the initial years".

Fourteen

Three times serving in Taiwan, the last time being local governor of Taiwan, Yao Ying (Mandarin) (1785-1853) says that "Taiwan was originally overseas land of savages, not a part of China. It was only claimed after we defeated Koxinga, but even then only 3 counties. Even at the end of Kangxi's rule, the northern half of Taiwan were still unruled savage lands".

Seventeen

In 1368 when the Ming Dynasty was founded, the first emperor Chu was quoted to state that "To the north-east, Korea. To the east-northeast, Japan. To the south-southeast, Taiwan".

He was also quoted to warn his descendants that they should not invade "the following countries: ..., Taiwan, ..." just because Ming was strong. Later in 1371, he was again quoted saying that Ming shall never invade these countries listed (which included Taiwan) unless they cause harm to Ming.

Twenty-one

In 1786 when Zhao Yi wrote his record on conquering Taiwan, the very first sentence on Taiwan's history states that "since ancient times Taiwan had not been part of China".

---

Obviously Taiwan had been called various names in the past, and my summary above, I've chosen to just use Taiwan partly because I'm too lazy to look up the English names, partly just to avoid confusing the reader.

Essentially, Taiwan was never considered "Chinese" territory until after Koxinga was defeated. And then even for a long time after that, Qing did not rule over the whole of Taiwan.

The myth that "Taiwan was always Chinese territory" was part of a propaganda push initiated by the KMT when they received Taiwan after the war. The PRC rode the bandwagon (hey, why not) and everything went south.

It became a part of mainstream history because nobody else resisted it. The only people who had any interest in the truth were under martial law (the Taiwanese people) for 38 years, so the myth settled nicely until recent years when it become alright to talk about the truth.