Prophecies about Tyre: Eze. 26:13-14 "So I will silence the sound of your songs, and the sound of your harps will be heard no more. And I will make you a bare rock; you will be a place for the spreading of nets. You will be built no more, for I the Lord have spoken," declares the Lord God. Eze. 26:21 "I shall bring terrors on you, and you will be no more; though you will be sought, you will never be found again," declares the Lord God.
If the prophecy about Tyre was refuted by Nebuchanezzar failing to destroy it, then why did Jesus bring up this memory, if it was a sore spot, and cast doubts on the power of God?
Luke 10:13-14 "Woe to you, Korazin! Woe to you, Bethsaida! For if the miracles that were performed in you had been performed in Tyre and Sidon, they would have repented long ago, sitting in sackcloth and ashes. But it will be more bearable for Tyre and Sidon at the judgment than for you."
This is just what Jesus' statement is about here, God's knowledge of the future, and also! About what would have happened, if things there had been different.
God can tell us not only about the future, but about how the past might have been, how it would have been, even when this involves people's choices.
"In point of fact, the mainland city of Tyre later was rebuilt and assumed some of its former importance during the Hellenistic period. But as for the island city, it apparently sank below the surface of the Mediterranean, in the same subsidence that submerged the port of Caesarea that Herod had built up with such expense and care. All that remains of it is a series of black reefs offshore from Tyre, which surely could not have been there in the first and second millennia B.C., since they pose such a threat to navigation. The promontory that now juts out from the coastline probably was washed up along the barrier of Alexander's causeway, but the island itself broke off and sank away when the subsidence took place; and we have no evidence at all that it ever was built up again after Alexander's terrible act of vengeance. In the light of these data, then, the predictions of chapter 26, improbable though they must have seemed in Ezekiel's time, were duly fulfilled to the letter--first by Nebuchadnezzar in the sixth century, and then by Alexander in the fourth." ("Encyclopedia of Bible Difficulties")
And "never be rebuilt" might be "all the current construction there will end," "Thou art not built up any more" (Young's Literal Translation), i.e. "it will not be built more," as in this statement:
Exodus 9:29 "As soon as I go out of the city, I will spread out my hands to the Lord ... there will be hail no longer..."
Which need not mean that there would never be any hail again in Egypt, rather it must mean that this current hailstorm would stop completely. Or here:
Nehemiah 2:17 Then I said to them ... "Come and let us build the wall of Jerusalem, that we may no longer be a reproach."
And Tyre does appear to have been destroyed: "Renan attributed the final devastation of Tyre to the onslaught of the Arabs at the end of the thirteenth century. From the ruins of the destroyed city [etc.]" ("Tyre through the Ages," p. 22)