I have been told that Teimanim today use the Nusach of the Rambam. So, what Nusach did they use before him? Does anyone use such a Nusach today? And is there a Siddur of such a Nusach?
Yemenites today use a siddur called 'Tichlal'. It is not accurate to call it the "nusach of the Rambam", while it does have many parallels. It also contains pieces from other sources, some predating Rambam. As @ezra astutely pointed out in the comments (even if only being clever) some, including the acclaimed R. Kafih, maintain that Rambam had referred to the Yemenite rite while arranging his own. Eventually, the two mirrored each other closely.
See here for a detailed essay on "who came first".
There is a consensus among academic researches that before accepting Rambam's nusach, Yemenite Jews used the nusach of Rav Saadya Gaon. This is based on multiple questions the Jews of Yemen sent to various poskim about switching. For details, see Siddur HaRambam published by Nosah Teiman. As mentioned above, Rav Yosef Kapach (Qafih) disagrees.