What is fundamentally physically impossible? Mathematical logic defines quite clearly what is true or false in math, and also that some theorems are impossible to prove. This resulted in some clear definitions of axioms set like Peano, ZF or ZFC, which are proved (or strongly believed) to be consistent, i.e do not allow to demonstrate both a theorem and its negation.
In physics, the distinction between axioms, postulates, principles and laws isn't clear at all. Some laws are linked to others, however not by simple derivation. For example the first law of thermodynamics is related to conservation of energy, which in turn is equivalent to the invariance by time translation by by Noether's theorem, which means (to me) it depends on the (perfect) cosmological principle.
We consider as "impossible" anything that violates any of those laws or principles, but are some violations "more impossible" than others because some laws are "stronger"?
For example thermodynamics or energy conservation are definitely unquestionable at our scale, but since they're connected to the cosmological principle at large scale (which can be criticized), are we sure they're "absolutely true"?
Are we sure the principles of physics are consistent, or might we end up with contradictions between, say, Einstein's principles and quantum mechanics?
And do we have something approaching Gödel's theorem in physics to assert that some things that we observe (dark matter?) are impossible to describe with our current laws, but that we need some more?
Well, I realize my question is actually several. Please answer with just a link or book reference if you think I should just read more. 
 A: This is a question of philosophy of science.
Some philosophers have held that generic principles, such as conservation laws, are more conventional than really true (neither true or false e.g. Wittgenstein viewed the principle of causality and perhaps all scientific laws  as a 'fishnet' for apprehending reality. Something that does not follow the principle of causality, he assumed, is not thinkable which does not entail that this principle belongs to the world itself) Poincaré also held conventionalist thesis.
The difference between logical and physical necessity is often casted in terms of an "analytic / synthetic" distinction, which terms goes back to Kant. Something is analytic if :
 - its contradiction is absurd
 - it is true in virtue of its meaning only (e.g. bachelors are unmarried)
These definitions are taken to be equivalent. Another view would be that analytic truth are logically necessary.
Something analytic can be thought of as a mere linguistic convention, or a tautology. Something is synthetic if it can be either true or false, depending on the world.
Kant thought that logical truth (the excluded middle) are analytic but not mathematical truth because, say, denying the 5th axiom of euclid geometry is not absurd. Mathematical truth are known by intuition.
Later, Wittgenstein and logical empiricists conceived of all logical, mathematical and conceptual (red is a colour) truth as analytic and all scientific truth as synthetic.
For them analytic equals necessary (but an analytic truth is purely tautological, it results from a convention) and synthetic equals contingent.
The analytic synthetic distinction was later criticised by Quine in 'two dogmas of empiricism', where he argued that because of confirmation holism (we always make more than one assumption when testing an hypotheses) the linguistic and factual components can never be clearly distinguished. Even mathematical and logical principles are put to test when verifying an assumption, although revising a logical principle when a test fails would be an extreme option (but he noted some have proposed to replace classical logic with intuitionist logic to solve some dilemma in quantum mechanics).
If Quine's arguments are sounds, there is some continuum between what is true in virtue of linguistic conventions (logic, generic scientific principles maybe) and what is true in virtue of the world (direct observations) with scientific laws in the middle. We can be pragmatic and assume that developing science and knowledge more generally amounts to picking the conventions which work well in interacting with the world.
EDIT: I'd like to develop a bit.
The main point, in my view, is that the more something is necessary (its negation is impossible) the more it can be interpreted as a definition.
The law of excluded middle (a is true or not-a is true) can be viewed as a profound principle, but it can also be interpreted as merely spelling out, together with other principles, what we mean by "not", "or" and "true". Some logicians have argued that intuitionist logic is not a revision of logic, but a change in definitions (with "provably true" replacing "true").
Similarly the cosmological principle can be interpreted as a profound principle on the nature of the world, but also as a mere definition of what we mean by "physical law" and if it turned out to be false there would certainly be a physicist to argue that what we discovered is simply that what we thought were physical laws were actually contingent facts, which are only valid in some parts of the universe, but that the principle is still true.
The same goes for the conservation of energy: it can be interpreted as a definition of energy as some quantity which is conserved over time.
What would really undermine these principles is if we discover that, e.g. there cannot be any physical law at all (maybe in virtue of another principle) but that would probably undermine the whole scientific endeavour as it is known today.
On the contrary, if you assume that all swans are white, then see a black swan, it is possible to say "well actually that's not a swan, since all swans are white.", that is, you can insist for white to be part of the definition of swan. But this is clearly not the more clever move. Which shows that swans are not necessarily white.
In conclusion, the question of whether something is more or less impossible/necessary amounts to a question of pragmatic: how much does it cost to change a definition or a feature attached to a concept? In the case of white swans, not much. In the case of a generic physical principle, a lot. In the case of logic or mathematics, it is not even clear we could still think properly about anything if we changed it.
A: I'll first discuss the difference between truth in Physics and Mathematics. 
In math's we invent a bunch of axioms and with our logic tools, we derive many theorems. But Physics, like it or not, has an experimental basis. We don't make arbitrary axioms/postulates/definitions, they are supposed to give some description of what we observe in real life. 
This means, that in Physics, something is true if it works (there are many more subtleties: it should be simple, accepted by a wide community, try to give some fundamental explanation, etc).  
For example, thermodynamics and energy conservation are violated at fundamental levels. But what matters is the scale. In its domain thermodynamics is perfectly valid, so is Classical Mechanics, QM, GR... You could say that they can't be proven wrong (possible but unlikely subtleties: we've been making all our experiments wrong, the Universe changes so much that our theories don't make sense (suppose all charge is destroyed, Electromagnetism would dissappear), etc.).
You can see that truth has a softer meaning in Physics. Some people might use truth in a rigorous sense, but they are the minority.
If we want to extend the domain of a theory to every process, we would need some TOE. And even then we can't know if it's true at a fundamental level.

We consider as "impossible" anything that violates any of those laws or principles, but are some violations "more impossible" than others because some laws are "stronger"?

Sure. Energy conservation in particle reactions, causality, Lorentz invariance...

Are we sure the principles of physics are consistent, or might we end up with contradictions between, say, Einstein's principles and quantum mechanics?

Contradictions are possible, but we hope it's not the case. IIRC, some quantum gravity theories (LQG) said that Lorentz invariance was broken.

For example thermodynamics or energy conservation are definitely unquestionable at our scale, but since they're connected to the cosmological principle at large scale (which can be criticized), are we sure they're "absolutely true"?

As I've said, they are false in a strict sense.

And do we have something approaching Gödel's theorem in physics to assert that some things that we observe (dark matter?) are impossible to describe with our current laws, but that we need some more?

We don't need nothing like Gödel. If our model does not predict some observed phenomena, that's enough to imply that our model fails.
In Physics, we just know truths on a particular range. Absolute truth is what  philosophy wants but never reaches. 
A: Let's build something fundamentally impossible as a macroscopic Second Law violation:
A hermetically isolated hard vacuum envelope contains two closely spaced but not touching, in-register and parallel, electrically conductive plates having micro-spiked inner surfaces.  They are connected with a wire, perhaps containing a dissipative load (small motor).  One plate has a large vacuum work function material inner surface (e.g., osmium at 5.93 eV).  The other plate has a small vacuum work function material inner surface (e.g., n-doped diamond "carbon nitride" at 0.1 eV).  Above 0 kelvin, spontaneous cold cathode emission runs the closed isolated system.  Emitted electrons continuously fall down the 5.8 volt potential gradient.  Evaporation from carbon nitride cools that plate.  Accelerated collision onto osmium warms that plate.  Round and round.  The plates never come into thermal equilibrium when electrically shorted.  The motor runs forever.
That is obviously Official hogwash, but why?  Alternatively, it is easy enough to build and observe not run (it won't run, for very good reasons not compromised by footnotes).  If it does run (it won't run, and not for subtle reasons), science changes.  Eventually a set of rules limiting operation of reality is complete, and fundamentally physically impossible operations are fully defined.
How do we know when that set of rules is complete?
A: IMO, there is nothing fundamentally physically impossible. Here is the simple version of what I understand how modern science works.
You have a set of theories. And you describe the world with it. Let's say the Newtons laws of motion. And you can say that according that theory, something is impossible. OK. But, you need to remember where does the theory comes from, and how it becomes one. A theory comes from observations, wrapped up into mathematical language. Nothing more, and nothing less. It is a mathematical description of what we do observe, and we can test it repetitively.
So when there is an experiment, that shows us, different results than theoretical predictions, then you say theory is wrong, or its application is limited. This is always truth. And you cannot prove that any physical theory is complete.
Another take on this is a simple statement that I have heard from some more or less established and famous fundamental physicists, that every physical theory must be falsifiable. (I think this is also a modern physics approach.) This has one great implication. There is nothing fundamentally impossible, since every theory must be possible to be disproved with an experiment.
Something fundamentally impossible, would be something impossible to observe. So something that we cannot test, or measure. I can only think of god and miracles.
Sidenote: I think that a good physicist will never rule out a miracle. However, it does not concern him, since it is a singular occurrence, and physics is about the possibility of recreating results in reality. In other words, if a physicist threw 100 stones in an experiment, and a deity would steal one from him, or displace, but the overall results would follow theory within the required statistical rigor, he would be happy with his theory. So far it works =) 
