Yes, we can imagine a universe without energy conservation. Just imagine that there's a dewar that's completely isolated from everything else, and there's an ideal gas inside. The gas suddenly gets hotter without any chemical change. Or imagine that all the electrons in the universe are gaining mass. Or imagine that there's an Energizer Bunny that never, ever stops.
More simply, imagine a universe with two states - one high energy and one low energy. If it ever changes states, then energy is not conserved.
These situations really do violate energy conservation. They would not be explained by bringing in some previously-unknown source of energy unless that source had some other, verifiable physical meaning.
Comparing a hypothetical perpetual motion machine to the neutrino is specious. The neutrino, a single particle, explained conservation of momentum, energy, and angular momentum in the reactions where it was involved - not energy alone. Still, people were indeed skeptical about neutrinos until they were directly detected. So the science behind neutrinos is not similar to a magical energy repository that exists simply to feed a perpetual motion machine.
If a perpetual motion machine were discovered, scientists would work very hard to find out where the energy is coming from. There's a good reason for that, which is that the laws behind everyday things are known, and those laws conserve energy, so most likely the perpetual motion machine really is drawing energy from some already-known source. If we ever discovered a true perpetual motion machine, though, we would not invent a new, unknown source of energy to add on to the universe to explain it. We would can the conservation of energy.
Something similar happened when it was discovered that in certain circumstances, the universe violates CP symmetry. Scientists did not invent otherwise-undetectable particles or in some other way invoke a deus ex machina to try to patch the situation up. It is simply accepted that the universe violates CP symmetry. Similarly, if we found energy is not conserved, we would have to acknowledge that time-translational symmetry is not perfectly true.
The point of energy conservation is to make useful predictions and help our actual understanding of the universe. Beginning with high school physics and continuing on through all the electromagnetism, quantum mechanics, analytical mechanics, relativity, and especially statistical mechanics that I've learned, energy conservation is an incredibly useful tool.
Specifically, it and other conservation laws provide constraints. If we know the state of a system now but don't know all the physics of that system, we might still at least calculate its energy. Then, either assuming the system is isolated or finding all the energy that goes in and out of it (all of which is transferred by known physical mechanisms), we know what the energy of the system will be in the future, even if we don't know exactly what the state will be. That's useful.
If energy could simply materialize in the system, then we could say "no worries; it just got some energy from the energy gods, who by the way are an established part of the scientific universe", but we'd be fooling ourselves because we'd have sacrificed the predictive power we used to have. I can't think of any case where energy is used in that way. Each time we claim energy enters of exits a system, it does it through a known mechanism that has a physical meaning. In the case of neutrinos, we could detect the neutrino leaving the system (with a certain probability). In the case of electromagnetic radiation leaving the system, we can detect that. In the case of the system losing thermal energy by conduction, we can detect the temperature change in the surrounding environment, etc.
In conclusion, it is not correct to say that we sacrifice Occam's razor to preserve energy conservation. In fact the opposite is true - positing the existence of the neutrino is a simple explanation for many different observed effects, not just the loss of energy when you ignore neutrinos.
I'm not knowledgeable enough to speak to your concerns with GR, so I'll leave that to the more experienced users.