I know Yechezkel writes about a Temple which is generally considered to be the Third. Is this explicitly identified as a Third Temple anywhere there? Otherwise, what's the earliest source that explicitly says there will be a Third Temple?
There is no 3rd Temple in a religious sense. It's a rebuilding of the second. The holiness of the second Temple is "sanctified for its time, and sanctified through to the future to come" -- ie all eternity. Just as we don't consider Herod's rebuilding and enhancement of the Second Temple to be a 3rd Temple, technically the messianic one will be a rebuilding of a Temple whose holiness is already there. Not a new Temple. It's only the nearly 2 millennial gap between them that make the language of "Third Temple" (בית שלישי) useful. But despite common usage, even in very notable primary rabbinic sources, it's not really meaningful on halachic or aggadic levels.
As to actually answer the question you were obviously trying to ask...
When neither the Great Assembly when they first built the second Temple, the Maccabbees and Herod when they rebuilt it conformed to Ezekiel's description, the notion that it must be rebuilt again became compelling.
So, aside from people deducing as much during the 2nd Temple, it was enshrined shortly after in the siddur. The prayer on Divine Service, said in the Temple (Tamid 5:1, quoted in Berakhos 11a), was adapted for the Amidah as the blessing that begins "Retzeih". In it, and many equally ancient quotes from the siddur, we ask G-d to restore the Temple and its worship. The request to return the service to the Sanctuary of Your House might date back to the Second Temple era, a request to restore those elements of First Temple worship that were impossible in the second. But more likely the words were inserted at the time it was adapted for post-temple use.
In addition, and codified in text only a couple of centuries even later, the laws of kings require that restoring the kingship would obligate him to make sure a Temple exists. Since there is none now, unless one comes down from heaven (Midrash Tanchuma, Pekudei 11), the messianic king would be obligated to build one (Jerusalem Talmud Megillah 1:11, Pesachim 9:1).