Must all physical theories conform to the laws of logic, such as being self-consistent? I am asking this because I once had an argument with a friend regarding the physics of time travel. I argued that any physical theory that allows time travel must have a consistent history. That is, no person or thing can go back in time to change what was the case, as that would mean that at some point in spacetime, both X and not-X happened. He argued that physics does not need to conform to logic or even be self-consistent. But what is the truth of the matter? I know that quantum physics has its own kind of logic called quantum logic, which differs from classical logic in some respects, but even there, I think physical theories should be at minimum self-consistent, and obey some basic logical principles.
As you note, coherence is a highly thought of screen to sort out bad theories, and few science theories are considered plausible if they do not satisfy it.
And yes, there are multiple logics, and satisfying classical logic is not the only possible one that a science theory could hold by. A science theory can instead satisfy an alternate logic from the basically infinite set of possible logics.
However, physics is a science, not a theory. It is just a field of study, and is filled with a collection of bottom-up theories developed to characterize specific phenomena. Physics itself is not coherent today. Its two most dominant theories, quantum mechanics and general relativity, are not coherent with the other. One of these theories is deterministic, the other is probabilistic. AND -- there are a variety of other local theories in physics that are not coherent with either of these major ones, primarily in the areas of solid state physics, and also in the field of emergent phenomena.
The non-coherence of science becomes even more apparent when one considers the other sciences. Evolutionary biology, for instance, does not reduce to cellular biology, and the concepts of ecosystem, ecological niche, breeding population, phenotype drift, etc., are meaningless at the cellular level, chemistry level, or physics level. Science as a whole is radically not coherent, and the SEP article on scientific reductionism in section 5 suggests it never will be.
This is discussed in a prior answer: Can findings in one science contradict those in another?
However, as you noted, coherence tests of science theories ARE STILL an important filter to toss out poor theories. And finding coherence within a science, and between sciences, remains a desirable goal. But as with all other areas of science, there are no absolutes. We may find that an incoherent model is our best explanation of some part of our world, and that as the SEP article implies, that incoherence in science as a whole and in each field may just be what our world is like.
Regarding logic in particular -- there is a major problem for all of the sciences as most logics require that A=A, the law of identity, hold. But over time, all of the objects, the A's, of science hypotheses, tend to change, such that A=/=A. Many of them change slowly, so that one can approximate A=A over short or medium time frames. But the lack of absolute A=A over time, makes all of science problematic relative to logics, as to apply a logic, all of its assumptions must be true, not just nearly true.
Physical theories are represenations of reality and as such - in order to have a meaning to us - must confront some way or another to the laws of logic, as you say. But physical reality - which is the real thing we are trying to represenat in a theory - does not have to obey logic: indeed, if that was the case, then everything that happens would be logical; but it isn't, or at least we are not always able to identify it as such.
Up to a point, yes, physics needs to be logical. Or to put it another way, a physics theory that was patently illogical would not get much traction in the physics community. However, you have to bear in mind that physics is a patchwork of theories that each tries to model a subset of observable phenomena, and the individual theories are not always mutually consistent. That said, the realty they attempt to model is self-consistent in many important respects, so an individual theory which led to conflicting outcomes would be immediately suspect.