I had prepared off-line an answer and question edit for "“Constructed in … during … by”, but the question was closed as too localized ("This question appears to be off-topic because asking what to write or asking for help rephrasing a sentence or passage are both off-topic here, as such questions are very unlikely to help anybody else."). Having applied my edit, I am tempted to vote to reopen, but I am a little concerned that I have made the question too broad (especially since my answer does not provide the depth and diversity of detail — it really should have used an additional example text for editing — that would be appropriate for a good answer to the question). If others think the edit makes the question appropriately broad, I would be willing to cast a reopen vote.
My (decent but quite imperfect) answer:
There are several ways to increase the readability of such sentences.
As CLockeWork's comment indicates, punctuation can visually organize a sentence into more manageable chunks. Isolating subordinate portions (e.g., "during the Dutch occupation in Taiwan" is subordinate to "in 1664") with commas, parentheses, or dashes is perhaps the most straightforward means of providing such structural markings.
Elimination of information that is unimportant or clearly implicit from context can further increase the conciseness and clarity of a sentence. In the example, "in Taiwan" is most likely redundant, assuming the construction was obviously in Taiwan and that "in Taiwan" is not being specifically used for emphasis or as a distinction. (Specifying "in Taiwan" might hint at John's nationalistic sympathies by recalling one more time when the Taiwanese people suffered from outside influences; by its greater precision and wordiness, using "of the coastal regions of southern Taiwan" would give more of an impression of John enthusiastically sharing his knowledge.)
Restructuring the sentence may also provide clearer organization while maintaining the desired flow. To work on such restructuring, it may be helpful to break the sentence into several choppy sentences:
it was constructed in 1664. It was constructed during the Dutch occupation. The Dutch occupation was in Taiwan. It was constructed by an admiral. The admiral had decided to settle on the island.
(Using a diagram of relationships may also help, but such might hinder the use of rephrasings that alter the relationships even if the meaning remains essentially the same.)
From this breaking up of the sentence, it is more obvious that perhaps too many things are linked to "constructed". Linking "during the Dutch occupation" more directly to "it" would reduce difficulty of keeping all the linked phrases close to "constructed". E.g.:
John said it was a remnant of the Dutch occupation in Taiwan, constructed in 1664 by an admiral who had decided to settle on the island."
Alternatively, since "during the Dutch occupation in Taiwan" applies to the admiral as the one doing the construction, it might be possible to link that content to "admiral". If it is appropriate to insert a causative implication (e.g., the construction is a residence), the following might be an appropriate rephrasing:
John said an admiral from the Dutch occupation in Taiwan constructed it in 1664, after deciding to settle on the island.
(This makes the decision subordinate to the date and definitively states a sequence and implies a causation, whereas in the original sentence the decision is more independent in timing and relationship. With this phrasing, it might be desirable to replace "it" with an appropriate noun since the antecedent has been made more distant.)
If the sentence is particularly long and unweildy, it may be appropriate to break it into multiple sentences or at least more separated clauses. If multiple sentences are used, a more desired sentence length might be achieved by adding new content or taking content from surrounding sentences. E.g.:
John said it was constructed in 1664 by a Dutch admiral who had decided to settle on the island. This architectural remnant from the Dutch occupation in Taiwan seemed [out of place/oddly comforting/almost oppressive] amidst its modern environment.
These examples show that when items are closely related it may be possible to change the direct links and so avoid having several items that should be close to a single directly linked item.
Modest redundancy can also make more complex sentence structures easier to follow. Even something as subtle and abstract as repeating a grammatical structure may help the reader mentally organize the sentence:
John said the building, which was finished in 1664 during the Dutch occupation in Taiwan, was constructed by a Dutch admiral who had decided to settle on the island.
(It is not clear whether the repeated use of relative pronoun clauses improves the structure or the greater separation from "which" — even without the commas — and "who" provides the structural assistance.)
In that example, the repetition of "Dutch" also seems to help hold the sentence together.
Of course, any such alterations must be made within the larger context. For example, long and somewhat breathless sentences may be used to express ethusiasm, in which case not using additional punctuation may be desirable, and a mild lack of clarity for the reader may even parallel a similar difficulty that the in-story listener is experiencing. In general, matters of style are not isolated to a single sentence and editing must consider the broader narrative and textual contexts.