What if it light just loses energy as it travels, so that the frequency shifts lower? That seems like a perfectly natural solution. How do we know it isn't true?

As gjm mentions, the general name for this sort of theory is "tired light." And these theories have been studied extensively and they are broken.

We have a very accurate, very well-tested theory that describes the way photons behave, quantum electrodynamics. It predicts that photons in the vacuum have a constant frequency and don't suddenly vanish. Nor do photons have any sort of internal "clock" for how long they have been propagating. As near as I can tell, any sort of tired light model means giving up QED in fairly fundamental ways, and the evidentiary bar to overturn that theory is very high.

Worse, tired light seems to break local energy conservation. If photons just vanish or spontaneously redshift, where does the energy go?

I can conceive of there being a tired light model that isn't ruled out by experiment, but I would like to see that theory before I junk all of 20th century cosmology and fundamental physics.

Most scientific theories, most of the time, have a whole bunch of quirky observations that they don't explain well. Mostly these anomalies gradually go away as people find bugs in the experiments, or take into account various effects they hadn't considered. The astronomical anomalies you point to don't seem remotely problematic enough to give up on modern physics.