Before I am inundated by myriad and vociferous claims that conservation of energy is the single most well-attested and experimentally verified principle in all of science, let me say that I am well aware of the ever-growing body of evidence which seemingly bears this principle out. However there seems to be, in my view at least, an abiding problem inherent to a principle of conservation with respect to how we could ever truly verify such a thing empirically. That no humanly constructed device can be perfectly accurate or precise is an incontrovertible and obvious truth. As a result, I am unsure as to how we could ever be sure that energy (or any other conserved quantity) is not being lost or gained (in defiant violation of physical principles) at length and/or time scales orders of magnitude below the resolution of our best instruments. I mean, how could we ever know? Ontologically speaking, it's almost inconceivable that energy could not be conserved. But epistemologically speaking, I am at a loss as to how we might ever verify—via experimentation or measurement—that energy is in fact being conserved to the precision guaranteed by a conservation law.
I will try to give a short introduction into the ideas of scientific truth as I understand them.
In mathematics, the world is beautifully simple. We have axioms that the set to be true, and from these we can deduce a plethora of statements to be undoubtedly true - given that the axioms are true. There may be undecidable statements about which we cannot say anything, but within axiomatic system everything is either true, false or undecidable.
Now, in reality, we are not in as comfortable a situation: We don't know the axioms the world is grounded upon, we try to guess them. The axioms we guess are what we call laws of physics. Now, given two different hypotheses (i.e. guesses for the laws of physics) $H_1,H_2$, we may look at some situation and, by logic alone, deduce that $H_1 \implies O_1$ and $H_2 \implies O_2$. Then we perform the experiment. If we observe $O_2$ not to be realized in reality, then, by the law of contraposition, we may conclude $\neg O_2 \implies \neg H_2 $, so the second hypothesis is clearly and unambiguously false.
But, suppose that, within the errors of our observation, $O_1$ holds. Then we cannot say that $H_1$ holds because $(H_1 \implies O_1) \implies (O_1 \implies H_1)$ is not a valid form of argumentation. All we can say is that our observation is compatible with $H_1$ being a law of nature, but it is not true in any rigorous sense. No statement about reality can ever be true in the axiomatic sense because of this reasoning.
Now, of course there could be a third hypothesis $H_3$ also predicting $O_1$. Then, until we perform experiments for which the hypotheses predict different things, $H_1$ and $H_3$ are equally true within our heuristic approach. And the more experiments we perform, the more often $H_1$ survives this process of constant enquiry, the more certain we grow that this is actually a good description of the world.
This is what science is all about: Taking the vast landscape of possible ideas about how the world works - take as a simple example Aristoteles' idea that everything wants to be at rest vs. Newton's idea that everything continues uniform motion unless acted upon - looking at the predictions these different ideas about the laws of nature make and then performing experiments eliminating those ideas that are false. Thus, we make a gradual progress towards the underlying truth, which is empirically inaccessible. The longer we perform experiment, and think of new hypothesis, the more refined will our laws of nature be, the greater our confidence can be that these are really good approximations to the way the world really works.
To say "We cannot prove it, we really don't know" is to vastly underestimate the power of falsificationism, and shows a callous disregard for the scientific method, whose success is reflected in every bit of technology around us.
[One may also find my answer to Why should a (physical) principle be applicable to different systems in different positions in space and time? to be relevant in this context.]
You may doubt that energy is conserved, but it is a direct consequence of Noether's theorem together with the assumption of time translation invariance, and this latter assumption is perhaps a bit more palatable/fundamental.
That is, it is mathematically true that if the outcome of an experiment doesn't depend on when we perform it, the quantity we call "energy" must be conserved. Therefore empirical evidence that physics is invariant in time directly and without any loss of strength evidences conservation of energy. Contrapositively, any evidence that energy is not conserved is evidence that something (either in the experiment or in the laws of physics) is changing in time.
I say this is more palatable because, at least for me, it's easier to believe in exactness when it comes to time translation invariance than when it comes to some mysterious "energy" being conserved.
It is more fundamental because physics is more about symmetries and their consequences than about listing laws and equations that have no justification beyond direct empirical results. If we do an experiment $X_1$ and get result $A$, then we predict that another instance of $X$, say $X_2$ will also result in $A$, not in $B$. Empirically we deduce from the first experiment $X_1 \Rightarrow A$, but it is symmetry in time (and space) that allows us to infer $X \Rightarrow A$, from which we predict $X_2 \Rightarrow A$. Evidence for the inferential generalization comes from all of physics, too. If we have experiment $Y_1 \Rightarrow B$, and generalization $Y \Rightarrow B$ holds for various instances $Y_i$, and similarly $Z \Rightarrow C$ holds, we have more confidence that $(X_1 \Rightarrow A) \Rightarrow (X \Rightarrow A)$ is valid.
Also, doubting time translation invariance leads to much deeper problems than violating conservation of energy. Even predictions that make no direct mention of energy would be called into question if the laws of physics change over time.
Finally, and more concretely, about the magnitude of potential violations of energy conservation: There can be violations that are presently undetectably small, but I argue that changes nothing. If you want to make quantitative statements rather than merely qualitative ones ("energy is conserved to within error $\epsilon$"), you should recast all of physics in the same form. Then no experiment ever has a result "energy is conserved." Instead all results are of the form "energy in experiment $E_i$ was conserved to within $\epsilon_i$." No matter how low we can push the upper bound on violations, we never infer, nor do we need to infer, that energy is conserved exactly. So your epistemological search for a justification for perfect conservation isn't needed, because perfect conservation isn't part of physics' ontology.
Let's assume that an experiment is performed that seems to indicate a violation of the conservation of energy principle.
Now, I suppose that it's logically possible that the experiment actually and unambiguously falsifies the principle in which case we must conclude that the principle is approximate and we must seek a deeper principle to guide our reasoning.
But, by being a physical principle, we mean that conservation of energy is not to be given up on lightly and that any experiment that seems to imply a violation will most likely
(1) turn out to be wrong
(2) indicate new physics (particles, interaction, etc.) that account for the missing energy
(3) motivate a broader conception of energy that remains conserved in the context of the experimental result
Regardless, we cannot eliminate the possibility that an experiment will be performed at some time that will falsify the principle.
Also, note that, in the context of general relativity, there are subtle issues even defining "energy" and "conserved". From the link:
It cannot be demostrated, but it can be checked.
This year I've done an experiment which verifies (indirectly) this principle. It is really easy: I take an iron ball, and I shoot it to a pendulum. As a result, the pendulum goes up, and I can measure the deviation angle after the collision. With a sensor, I'm also able to measure the initial speed of the ball. And of course, I can measure all the masses (the ball and the pendulum).
Now, I use the masses and the initial speed, and I make two assumptions: the momentum is conserved (there's no external forces) and energy is conserved.
Using this two assumptions, I can calculate the angle moved by the pendulum, which is pretty similar to the angle I measured. So, my two assumptions must be correct and energy is conserved.
Well, this method only proves it for a particular case, not for every physical system. However, another experiments can be done in other physics areas (waves, thermodynamics, etc) to check it. But, as they've pointed in the comments, we cannot demostrate it. We have stated it, and we only can check that's true for lots of particular systems. However, we may find a system where this is not true; in that case, we will have to change this statement. That's why we call it a principle: we cannot demostrate it, but we believe that is universally true, seeing nature. We cannot demostrate that is false.