This answer relates to the following clarified question from the OP in comments:
But how can we prove a statement is not self-referential? And even if we can, how can we prove a given statement is not some other type of statement (like self-referential) that also doesn't work under LEM (a new type that would should ban too)? Sounds like all we can do is assume it works until shown that it doesn't, which doesn't sound very mathematical.
This question has a long history. It occurred to many other mathematicians, especially in the 19th century, when within 100 years they (1) learned of the independence of the parallel postulate in geometry, (2) learned of the ambiguity of the previous foundations of calculus and real analysis, and (3) learned of set-theoretic paradoxes such as Russell's paradox.
The quoted question really comes down to the consistency problem: how do we know that the systems we work with are consistent? Unfortunately, the generally accepted answer is that, to some extent, we do have to "assume" consistency. That may sound unfortunate at first, but it does not turn out to prevent us from doing math. I will explain a little more.
The natural idea was that, as a first step, we should make sure that the systems we work in are fully specified, unlike natural language. This led to the development of formal logical systems such as first-order logic, and formal foundational theories such as Peano Arithmetic (PA) and Zermelo-Fraenkel set theory (ZFC). These systems are unambiguously specified, so that the question of their consistency is a precise mathematical statement. (This is not the case with natural language, which is not fully specified.)
Now, we can ask: is it possible to prove that a system such as PA or ZFC is consistent? This is related to "Hilbert's program" pursued by David Hilbert and colleagues in the early 20th century. There was a lot of progress on that question, including the famous "incompleteness theorems" of Kurt Gödel.
There are many theorems related to the problem. For example, there are two independent proofs (by completely different methods) of the consistency of PA. But both of these proofs do require nontrivial axioms or deduction rules to carry out. If we wanted to prove the consistency of those axioms or deductive rules, we would need to assume some other axioms or deductive rules. In the end, you have to take some axioms for granted, or you have an infinite regress.
Mathematicians differ on how to interpret this situation. Some mathematicians view the consistency problem as solved, in that they either view PA and ZFC and being sufficiently "proved" consistent, or they view it as impossible to prove and thus not a mathematical question. Others think that the consistency of PA and ZFC is still an open problem which might be resolved in the future.
This situation is not as bad as it may seem, however. Here is a common viewpoint among mathematical logicians today.
First, we have been working with PA and ZFC for a long time, and despite many efforts, nobody has found a contradiction in them. So, heuristically, they seem to have stood up to the test of time. We don't have any proofs of their consistency with "no" assumptions, but we do have several proofs of their consistency "with" assumptions, and these proofs at least help us see what else would have to go wrong in order for these systems to be inconsistent.
Second, if we did find a contradiction in a well known foundational system, it would be extremely interesting, because it would show us something we didn't know before. The most likely outcome is that we would modify the formal systems to avoid the new kind of paradox, and we would publish a lot of logic papers analyzing that paradox.
Most logicians believe that discovering an inconsistency in our foundational systems would not "break" mathematics, because most ordinary mathematics can be done in many different formal systems, so we would still be able keep all or almost all of the results of ordinary mathematics, although we might formalize them differently.
Going back to LEM in particular, there is another result of Gödel relating to Peano arithmetic and its cousin without excluded middle, Heyting arithmetic. Gödel showed that there is a completely effective procedure (an algorithm) that would take any formal proof of an inconsistency in Peano arithmetic and transform it into a formal proof an inconsistency in Heyting arithmetic. So, in the case of Peano arithmetic, if there is somehow an inconsistency, it isn't from LEM. This is just one of many, many theorems about the consistency problem.