Why is global conservation of energy not considered a tautology?
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.
The issue is finding that conserved energy. What Noether's theorem does is give us a nice, clean way to discover what the conserved energy is.
It turns out that for certain models in general relativity, there is no clear global notion of conserved energy. In particular, most of the "nice" ways that we would try and define energy are totally coordinate-dependent--both the components of the metric tensor and their first derivatives are right out as local components of a potential "energy of the gravitational field," since their value at a point can be set arbitrarily by a coordinate transformation, meaning that if I were to construct an energy density out of the metric and its first derivatives, its value would depend on whether I used (for example) spherical or rectangular coordinates in $\mathbb{R}^{3}$ There are some cases where we can be saved by Noether-type logic, though--if we either have a metric that has a global timelike translation symmetry, or at least a 3-surface that has a timelike or null translational symmetry along it, we can construct something that looks like a conserved energy for the dynamics in that spacetime. These different 'masses' go by different names, depending on the details of the problem that you're dealing with. For the sake of posterity, I'll refer to a pretty technical paper on this.
But, it turns out that there are a wide variety of spacetimes where none of this works out, and that expansionary cosmologies containing matter other than the cosmological constant are one of these type of spacetimes.${}^{1}$. In these cases, there is just no conserved energy or energy density that we can define. If the universe expands forever, and the photons just keep on redshifting, where is the energy of those redshifting photons going to, after all?
We just have to deal with the fact that the only energy conservation we have is in the local sense, where $T^{ab};{}_{b}=0$. Globally, energy is not conserved.
${}^{1}$In much the same way that there is no conserved energy for the Lagrangian $L=\frac{1}{2}m{\dot x}^{2} + a_{0}xe^{t}$. It's just that in this case, we know that it's because we have a time-dependent external potential driving the system, so we don't expect the energy to be conserved.
If you observe that energy is not conserved as in the perpetual motion example you give, you cannot just proclaim that there is somewhere else that the energy comes from. That would provide an empty concept of no value. You must find a dynamical system such as a new type of particle or wave and define energy as a function of the variables of the new dynamical entities in such a way that it accounts for any missing or excess energy.
To give an example, binary pulsars are observed to be losing energy when you add up the known forms of energy within the system. This is resolved by showing that the energy in radiated gravitational waves predicted by general relativity can precisely account for the missing energy. This is verified experimentally and will be confirmed more directly when gravitational waves are detected and found to transfer energy back to matter in accordance with the predictions. If they don't then energy conservation will be in trouble.
Noether's Theorem merely gives a way of showing that energy conservation laws of this sort exist when the dynamical laws are derived from a principle of least action that has time invariance. Einstein first formulated a correct law of energy conservation for gravity without using Noether's theorem and his result is still correct, although there was a long history of arguments before the matter was finally agreed. GR has time translation invariance as a subgroup of diffeomorphism invariance when you treat the gravitational field as a dynamical entity itself. Noether's theorem applies in this case and energy conservation can be derived in that way too.