If photons don't "experience" time, how do they account for their gradual change in wavelength?

We don't really have a good perspective on what a photon "feels" or, indeed, anything about what its universe would look like. We're massive objects; even the idea of "we must travel at the speed of light because we're massless" makes little sense to us. But we can talk, if you like, about what the world looks like as you travel faster and faster: it's just that obviously that doesn't tell us truly what happens "at that point" of masslessness.

One thing that happens, as you go faster and faster, is that everyone else sees your clocks ticking slower and slower. This is the basis for the statement that photons don't "experience time." It's a little more complicated than that: suppose you are emitting light, say, as periodic "flashes": there is a standard Doppler shift which has to be corrected for before you see this "time dilation". In fact, as you get faster and faster, the flashes undergo "relativistic beaming", the intensity of the pulses will point more and more in the direction that you're going, as seen from the stationary observer.

The same effect in reverse happens for you: as you go faster and faster, the stars of the universe all "tilt" further and further into the direction you're going.

By these extrapolations, in some sense a photon experiences no time as seen from the outside world. But in another sense: if the photon had any way to communicate to the rest of the world, it could only communicate to the thing that it's going to hit anyway, and no faster than it itself can travel there. So in some sense it simply "can't" communicate its own state at all.

So a key lesson, I guess, is that we have to think of the particle's frequency as interactive: in some sense the photon's energy that gives it a frequency $f = E / h$ where $h$ is Planck's constant, but in another sense it is changeless, it's not "oscillating."

Quantum electrodynamics actually reifies this notion (makes the idea "solid" in the mathematics) pretty well: the photon's frequency lives in its complex phase, but a quantum system's overall phase factor is not internally observable and can only be observed by its interaction with an outside system with a different phase. In turn, you only observe their phase difference; there is a remaining overall phase for the interacting system which becomes unobservable, and so forth.

In Minkowski spacetime, the spacetime interval of lightlike movements is zero. That means, from the (hypothetical) point of view of a massless particle such as a photon, it does not even exist one Planck time.

At a proper time zero, any wavelength becomes meaningless, even if the physical process is the same that we observe. For the answer you have to take into consideration cause and effect: The photon including all its features has been created by an electron at A, and features have been transmitted to an electron at B. If from the (hypothetical) point of view of the photon it is vanishing, you have to refer to what is remaining, i.e. the electrons A and B.

Electron A is transmitting a momentum to electron B, and (due to space expansion) electron B is receiving a diminished momentum. From the (hypothetical) point of view of the photon, between A and B there is nothing (spacetime interval = zero).