It is rather curious that the head of state of the Romulan Star Empire is titled the "Praetor," considering that the praetor was a mid-ranking
magistratus ordinarius (ordinary magistrate), not a particularly high-ranking one.
The three magistracies in the
cursus honorum were the quaestorship, the praetorship, and the consulship. Quaestores and praetores could be assigned to govern major provinces, but more frequently gubernatorial posts were assigned to former
magistratus ordinarii (Iulius Caesar was proconsul in Gallia Cisalpina, Gallia Transalpina, and Illyricum, immediately following his first consulship with Marcus Calpurnius Bibulus).
Although in very early Roman history, the consules were occasionally called praetores, it is quite clear that consular dignity was superior to praetorian dignity; when the consulship was held by a college of
tribuni militum consulare potestate (military tribunes with consular power), it was always the consular authority that was invoked.
Again, the authoritarian so-called Second Triumvirate (Marcus Antonius, Caius Iulius Caesar Octavianus, and Marcus Aemilius Lepidus) were formally called
triumviri rei publicae constituendae consulare potestate (triumvirs for the reorganisation of the republic with consular power).
Of course, those titles became largely superfluous under the Caesar Augustus's Principate. Most provinces were governed by officials called praefecti (prefects), who were appointed by the emperor. Still, consules ordinarii continued to be elected until AD 541, when the emperor Iustinianus decreed the abrogation of the office. There were, of course, several other examples of one man's having held sole consulship: The emperor Constantinus III (Imperator Caesar Flavius Claudius Constantinus Augustus) was sole consul in the West in AD 409, for example.
If the Romulan Star Empire were to be a stellar counterpart to the Roman Republic, it would be more appropriate for the head of state to be titled consul. Note that it is not strictly necessary for there to be two consules; Cnaeus Pompeius Magnus was elected sole consul for 52 AC, and his archenemy Iulius Caesar was elected sole consul for 45 AC (although both constituted unusual concentrations of power in one man's hands -- unsurprising, considering that it
was Pompeius Magnus and Iulius Caesar).
As to what would be the appropriate title for a stellar counterpart to the Roman emperor, that is a difficult question, as the Romans themselves never had a very clear idea of what the emperor should be called.
The most commonly seen title --
imperator (loosely, commander) -- is by no means exclusive to the emperors. As a title, it far predates the Principate; if a particular officer had command over many legiones, his title was
dux (leader), and the commanders of his component legions
legati (legates). When that general secured a particularly spectacular victory, his soldiers proclaimed him imperator, an honorific title with no particular meaning.
The first emperor, Caesar Augustus, was an imperator, but he never used that title to symbolise his office, nor did any of his immediate successors. For example, Tiberius Iulius Caesar, the second emperor, was not the only imperator to have lived during his reign: His much more popular consanguine Germanicus Iulius Caesar was also an imperator, though he was not emperor.
As the Romulans are generally portrayed as a more political race (as contrasted with the truculent and feudal Klingons), one would suppose that the title imperator would be inappropriate, given its militant connotation -- properly, the title suggests military authoritarianism, such as that of Manuel Antonio Noriega, or, in the
Star Trek context, the Cardassian Union.
The second most common title is princeps, which is an abbreviated form of
princeps senatus (first man of the senate). It, too, predates the Principate, and is not at all unique to the emperors, being merely an honorific title that literally meant the bearer was listed first on the rolls of the senatus -- the notion being something along the lines of "first among equals," or a certain primacy of honour (not authority). There were no fewer than six principes senatus prior to Caesar Augustus.
Offhandedly, of course, one might guess that princeps senatus would be appropriate for the Romulan Star Empire, given its particular emphasis on the Senate as a college of statesmen, not simply as a deliberative or legislative chamber.
The words Caesar and Augustus are frequently taken as titles, but the fact of the matter is that both are actually names, not titles. How, exactly, those names became permanently associated with the imperial dignity is a rather long and complicated subject, but suffice it to say that these, perhaps the most popular "titles" for the emperor, are completely inappropriate for use by the Romulan Star Empire.
Of course, one should also note that this is
Star Trek, and the names of institutions are poor indicators of how they are governed. Witness the Klingon Empire which seemingly for centuries lacked an emperor, and was ruled monarchically by the Chancellor of the High Council, a title equivalent in meaning to prime minister or premier -- a head of government, but not a chief of state!
It is not altogether surprising that the head of the Romulan state is not an emperor or empress. This is the same franchise that cannot seem to decide whether the United Federation of Planets is governed by the President or by the Federation Council -- and that has uniformed, commissioned officers in the Federation Council!
In response to the original question, if one does not presuppose the coup d'état that accompanied Shinzon's eradication of the Senate:
The Constitution of the United States provides in Article I, section 2, that, in the case of the House of Representatives, "[w]hen vacancies happen in the Representation from any State, the Executive Authority thereof shall issue Writs of Election to fill such Vacancies."
The Seventeenth Article of Amendment provides that "[w]hen vacancies happen in the representation of any State in the Senate, the executive authority of such State shall issue writs of election to full such vacancies: Provided, That the legislature of any State may empower the executive thereof to make temporary appointments until the people fill the vacancies by election as the legislature may direct."
Essentially, the United States Government would continue to operate normally, even if the entire Congress were to have been eradicated in one swift stroke, as the mechanism whereby a new Congress may be elected is already in place.
The matter of Presidential succession is a bit lengthier. One may read
3 U.S.C. 19 to learn the Congress's thoughts on the matter.
Under no circumstances would a State governor assume Federal office by succession. Since the Seventeenth Amendment was ratified in AD 1913, there has been no formal connexion between the State governments and the United States Government: The one cannot "chuse" the members of the other, or depose or otherwise remove them, except on a provisional and temporary basis in the case of United States Senators. (Prior to 1913, the State legislatures selected their United States Senators, per Article I, section 3.)
The only connexions remaining are the temporary appointment of United States Senators, and the selection of the members of the Electoral College, which remains in the hands of the State legislatures -- however, the Electoral College is not an apparatus of the United States Government, but rather a specific subset of the electorate. States cannot force their Electors to vote in any manner.
Of course, the entire discussion is a bit pointless, because it ignores the fact that Shinzon was praetor not simply because he eradicated the Senate, but, more importantly, because he was the leader of a coup d'état. Such leaders can generally call themselves whatever they like; it is precisely how Napoléon Bonaparte acquired the title of "First Consul," and then of "Emperor of the French."
In an example of how history occasionally has a sense of humour, one finds that the French have provided another example of how there need not always be two partners in a consulate: Bonaparte's had three (himself, Jean Jacques Régis de Cambacérès, and Charles François Lebrun).