With redshift, energy is lost. Where does it go? A photon emitted by a distant source billions of light years away arrives here with a lower frequency hence less energy than it started with. What happened to the energy?
 A: The energy of a particle is an observer-dependent quantity in General Relativity. For a particle with four-momentum $ P^\mu $, measured by an observer with four velocity $ u^\mu $, is defined as:
\begin{equation}
\mathcal{E}^{(u)}=-g_{\mu \nu}u^{\mu} P^{\nu} >0
\end{equation}
For instance, for a static observer  $ u^\mu_{st} =(1,0,0,0) $ in Minkowski space-time, we have:
\begin{equation}
\mathcal{E}^{(u_{st})}=-P_0
\end{equation}
That is constant, and the energy is conserved. But this is not true in general. If the four velocity is time dependent, like in an expanding universe, the energy is not a conserved quantity. You can find from the geodesic equation (using the Robertson-Walker metric) that  the velocity is inverse proportional to the cosmic scale factor, so decrease with time.
From another point of view, you can say that is the time dependence of the metric that breaks conservation of energy.
At the end it really depends on the definition of energy you want to use. Very often in the definition of energy you need a time-like Killing vector field to have a constant energy. But the Robertson-Walker metric doesn't admit such a vector field.
A: No energy is lost.  The photon does not change, we just perceive it differently because of our relative velocities.  The doppler effect is not a change in a wave, just the change in the apparent frequency of the wave.  Technically speaking, the doppler effect changes the wavelength of the wave, which alters the apparent frequency, which is why waves get red- or blue-shifted.  $E = hf$, so since the frequency of the photon does not change (again, only the frequency we observe changes), the energy does not change.
Another way to imagine it is that, for an observer at any distance from the star but moving with the same velocity we do, the light will always be redshifted no matter how far it is from the star/galaxy.  Since the observed frequency of the light does not change, the energy cannot have changed. 
A: Let us take a simple redshift of a  spectral line from a moving galaxy. This means we are dealing with special relativity equations. 

In the center of mass system of the  excited atom ("deexcited-atom and photon" )the spectral line is fixed if our rest frame coincides with the rest frame of the atom . We observe it as at the star level on the left of the image. 
The next line from the bottom is a nearby galaxy, this galaxy is moving, and so  the rest system of the atom is moving with respect to us. We see the photon with less energy and if we could measure the deexcited atom we would see it balance the energy. In relativistic speeds one should use the special relativity equations.That is how we find that the galaxy is moving after all! 
It is similar to shooting from a moving train: if ahead the bullet will gain energy from the train, if behind, the train will gain energy from the bullet and the bullet will be slower. For an observer at rest on the ground the two bullets will have different energies even though the gun shoots with the same energy at the rest frame of the train.
These redshift observations led to Hubbles law, 

Hubble's law is the name for the observation in physical cosmology that: (1) objects observed in deep space (extragalactic space, ~10 megaparsecs or more) are found to have a Doppler shift interpretable as relative velocity away from the Earth; and (2) that this Doppler-shift-measured velocity, of various galaxies receding from the Earth, is approximately proportional to their distance from the Earth for galaxies up to a few hundred megaparsecs away. This is normally interpreted as a direct, physical observation of the expansion of the spatial volume of the observable universe.

My argument above relates to reference frames and does not discuss expansion of space itself as in cosmological models. As far as measurements go I do not see why it would not hold, that the atom moving away from us and the photon arriving in our detectors have to balance the energy , after all each photon signals a single interaction. It is all a matter of reference frames, imo. 
