If conservation of energy was wrong, how would we know about it? Suppose you just started learning physics and you've been introduced to conservation of energy and kinetic energy. Apart from those concepts you know next to nothing. Then you observe an inelastic collision. You measure the speeds of the objects before and after the collision and you are puzzled because kinetic energy is the only form of energy you know and you see it's clearly not conserved. You conclude that either:
a) Conservation of energy is wrong.
b) The formula $E_k = mv^2/2$ is wrong.
c) There is some other form of energy you didn't account for.
HOW do you know which one of those scenarios is true? Can you measure the total amount of energy contained in those two objects before and after the collision and reassure yourself that everything is okay, energy hasn't gone anywhere, it just changed its form? If you observe an object that seems to gain energy from nothing, how will you know whether conservation of energy fails or there is some undiscovered form of energy that you don't know how to measure yet?
 A: We don't know! If we were to observe a situation where energy conservation did not appear to work, that would be a major puzzle. As you say, either we would have to discover some alternative contribution to the energy that we had been neglecting, or we would have to give up on energy conservation. A priori it is not obvious which one of those two resolutions would be correct.
In practice, we have a very strong theoretical prior to believe in energy conservation, and therefore we would try very hard to find possible contributions to the energy that we had neglected. However, one can imagine a situation where we find that every way we try to save energy conservation failed. In that case, we would have to seriously consider giving up on energy conservation. This would mess with our understanding of physics in a very serious way, as other commenters have discussed, and its hard to imagine a consistent framework of physics that doesn't have energy conservation but is still consistent with all the tests of the standard model that we already have. However, if that's the way nature is, then so be it.
Two interesting historical examples of this form:


*

*The neutrino. When studying beta decay it appeared that energy could not be conserved. The neutrino was proposed as a very light, weakly interacting particle who's only role at the time it was proposed was to save energy conservation.

*E/M. If you try to study the forces between moving charged particles (ie, not electrostatics or magnetostatics), you end up discovering that momentum conservation is not obeyed, if you only look at the momentum of the particles. The resolution in this case is that the electromagentic field itself carries momentum, and when this is included momentum is conserved. 
A: Noether's theorem states that to every continuous symmetry of a physical system there is an associated, conserved quantity. The conserved quantity associated with time translation invariance (i.e. it doesn't matter if you perform an experiment now or tomorrow, provided you set it up the same way) is what we call energy.
Therefore, somewhat tautologically, it cannot happen that energy is not conserved (in classical mechanics, anyway). Your scenario a) is avoided by definition. Let the Feynman speak:

There is a fact, or if you wish, a law, governing all natural phenomena that are known to date. There is no known exception to this law—it is exact so far as we know. The law is called the conservation of energy. It states that there is a certain quantity, which we call energy, that does not change in manifold changes which nature undergoes. That is a most abstract idea, because it is a mathematical principle; it says that there is a numerical quantity which does not change when something happens. It is not a description of a mechanism, or anything concrete; it is just a strange fact that we can calculate some number and when we finish watching nature go through her tricks and calculate the number again, it is the same.

If the stuff we currently think of as energy is not conserved in time, then we must conclude that there is "a form of energy" yet unknown to us (your scenario c)). Kinetic energy is not wrong because you can simply derive the Noether charge/energy of a freely travelling particle and see that it is indeed the kinetic energy we know. You might object and say that "kinetic energy" might need to be redefined to include the new term instead of calling it something new - but then again, the partitioning of the energy into "different kinds" is artifical anyway, since, from the Noetherian perspective, there's just energy, i.e. that which is conserved.
