Why is thermodynamics beyond doubt? Eddington once gave the following quote:

The law that entropy always increases, holds, I think, the supreme position among the laws of Nature. If someone points out to you that your pet theory of the universe is in disagreement with Maxwell's equations—then so much the worse for Maxwell's equations. If it is found to be contradicted by observation—well, these experimentalists do bungle things sometimes. But if your theory is found to be against the second law of thermodynamics, I can give you no hope; there is nothing for it but to collapse in deepest humiliation.

What did Eddington mean by this?  Why did he give a special status to the Second Law of Thermodynamics?
 A: They  said this in a certain context , and the statement you are making has been taken out of context.
As a general principle, ALL  physics can be doubted . There are not many holy cows in physics.
But, what it means to "doubt" something in physics is different than the colloquial usage of the word "doubt" that is often used by crackpot theorists.
Some theories have more levels of "credence" attached to them than others, which is a direct result of being able to describe and predict observations, better than other theories, in their domain of the natural world.
During the time of Eddington and Einstein, thermodynamics definitely had more "credence" than some other branches of Physics.
Also remember Einstein is just one scientist among many others. He was great in his topic of expertise, but he was not necessarily correct about everything.
A: 
Why thermodynamics is beyond doubt?

Because it fits experimental data and is predictive , i.e. new data and systems are predicted for experiments, with small errors. Within its mathematical domain of applicability.
Einstein is not the Pope, neither is Eddington. For example Einstein is  is quoted

Quantum mechanics is very impressive. But an inner voice tells me that it is not yet the real thing. The theory produces a good deal but hardly brings us closer to the secret of the Old One. I am at all events convinced that He does not play dice.

At present, mainstream physics posits that the underlying layer of physics is quantum mechanical. Physicists still exploring deterministic underlying theories are in a small minority. Still, even if they are  proven right, the theory they come up with must embed the quantum mechanical observations at the phase space quantum mechanics  has been found valid. (actually I should say"if new deterministic theories are validated by data and observations, "proof" has no meaning in physics, only in mathematics)
The real criterion for "credence" discussed in the other answer, is: reproducing data and predictivity of new.
A: While the other answers brought important clarifications about the context and what exactly was meant, this is a rather interesting question to ponder in its own right.
In this case we have to make a distinction between thermodynamics, which is a theory based on the empirical facts, and statistical physics, which is a result of logical reasoning. In other words, we have to make distinction between a law of nature and a human-made theory. It is very likely that the authors of the quote meant the latter.
While an empirical theory is always at risk of being contradicted by an experiment, undermining mathematical proofs is much more difficult - unless there are errors in the proofs, this requires questioning the underlying axioms. Indeed, relativity and QM came into existence by questioning the underlying assumptions of Newtonian mechanics. Statistical physics is built essentially around counting the number of available states and some general assumptions about the accessibility of the states (such as ergodicity). Specifically:

*

*We know exactly what these assumptions are and where the conclusions of statistical physics would not hold

*Within the range of applicability of these assumptions, the theory is as good as our logical reasoning.

In other words: it is okay, if something contradicts known facts, it is not okay, if it contradicts logical reasoning. (From the point of view of physics, obviously.)
Update
It is worth adding the Einstein's full original quote which makes the same point:

A theory is more impressive the greater the simplicity of its premises is, the more
different kinds of things it relates, and the more extended its area of applicability.
Therefore the deep impression which classical thermodynamics made upon me. It is the
only physical theory of universal content concerning which I am convinced that, within
the framework of the applicability of its basic concepts, it will never be overthrown.

