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".