In the times of Ezra and Nechemia the temple was rebuilt. Rambam codifies that the mitzvah to appoint a king comes before the mitzvah to build the temple. If that is the case why didn't the Jews appoint a king (perhaps in secret to avoid political backlash) before beginning to rebuild the temple?
Some commentators say that Zerubbabel was supposed to be king (such as Ibn Ezra, see e.g. his commentary to 4:14). Zerubbabel is never explicitly called a king, but he was from the royal family (1 Chronicles 3:19), and also served as governor (פֶּחָה) of Judea (Haggai 1:1).
So it seems that the Judeans did appoint Zerubbabel as king, or at least tried to do so, before rebuilding the Temple. It's true that his position as governor didn't pass to his descendants like kingship normally does, but that was only clear after the fact.