In a comment to the last post Anon1 referd to a statement by R' H. Shachter based on a Ramban in P' Korach that the requirement of the mitzvah of malchus is to establish a Jewish government, not necessarily a Jewish monarchy. I do not have this sefer of R' Shachter's to check the source, but my guess is that the Ramban in question is 16:22 (if not, this post can stand on its own.) The Ramban writes that Bnei Yisrael were guilty of delaying the building of Mikdash because they failed to seize the opportunity to start construction in the days of the shoftim. Instead, they waited until David HaMelech took the initiative. The Ramban's comment seems puzzling in light of Sanhedrin (20) which which presents the order of mitzvos Bnei Yisrael must perform upon entering Eretz Yisrael. The gemara writes that first the mitzvah of appointing a King must be fulfilled, and only afterwards can the mitzvah of building a Mikdash begin. If so, during the days of the shoftim, when no king had yet been appointed, there did not yet exist the possibility of starting construction on the Mikdash. How could BN"Y be accused of delay? QED, some (possibly R' Shachter) would argue, according to Ramban the shoftim were considered a fulfillment of the mitzvah of malchus by virtue of being a Jewish government.
It is possible (see Margoliyas haYam Sanhedrin 20:20) to salvage the Ramban without necessarily being forced to such a sweeping conclusion. Perhaps we can distinguish between the need for malchus as a prerequisite for binyan Mikdash, for which any form of Jewish government suffices, and the mitzvah of establishing a monarchy as an indepedendent goal in its own right, which might demand specifically the appointment of a king.