"Every politician in this circle will have a firefighter to their immediate right" is typically coded into predicate calculus as ∀x∃y(P(x) → F(y)∧IR(x,y)). If there are no politicians in the circle P(x) is always false, and, by the convention about the material conditional, when the premise is false the conditional is true. So it is not that the proposition can not be proven, it is that the conditional "defaults" to true by the convention about false premises. That firefighters tell the truth will then be true in this case, but there is no need to assume that they always do.
This said, one can instead interpret conditionals existentially, and insist that objects spoken of in the premise must exist. This is related to the question of existential import that was much discussed by logicians in 19th century. Under the (modern reading of) existential import one makes a different translation of the sentence into the predicate calculus, one that explicitly adds the existence claim. Namely, ∃xP(x)∧∀x∃y(P(x) → F(y)∧IR(x,y)). In this case in the absence of politicians the proposition comes out as false. But this interpretation is almost never used today.
Ironically, the historical discussion was not about whether universal propositions (like "all politicians are liars") imply existence, but whether particular ones do (like "some politicians are liars"). On modern view the only way to express such propositions is by using the existential quantifier, so the answer is trivially yes. But in Mill we read
"That the employment of [the word "is"] as a copula does not necessarily include the affirmation of existence, appears from such a proposition as this: A centaur is a fiction of the poets; where it cannot be possibly implied that a centaur exists, since the proposition itself expressly asserts that the thing has no real existence". (System of Logic I.iv.1)
The modern view was introduced by Brentano in 1874, who argued that "sick man" is just a combined concept with no existential import, but it becomes more when "is" turns it into a sentence. So "some man is sick" has the same meaning as "sick man exists". Even before that in private correspondence Brentano managed to convince Mill, who wrote in 1873:
"You did not, as you seem to suppose, fail to convince me of the invariable convertibility of all categorical affirmative propositions into predications of existence. The suggestion was new to me, but I at once saw its truth when pointed out."
But the real reason for the triumph of Brentano's view is that it fits the modern predicate calculus. As for centaurs and other fictions, some artificial devices have to be deployed, like paraphrase or a separate existence predicate, see What are the counterexamples to Kant's argument that existence is not a predicate?