You really should split your question. I will answer the part where you do not understand how counting of degrees of freedom work.
Basically we count the number of propagating (physical) degrees of freedom per point of spacetime. Of course, the total number of degrees of freedom is infinite because spacetime is continuous and has an infinite number of points, but to ask for the number of degrees of freedom per spacetime point is a reasonable demand to make. Bear in mind that we only care about physical degrees of freedom by which we mean those that can be properly normalized.
You correctly state that photons can be off-shell but they are only those involved in internal processes. External photons are always on-shell. Moreover, gauge invariance is a physical property. External fields which you measure in your laboratory should be independent of your chosen gauge. In other words, the S-matrix should be gauge-invariant. On the other hand, there is nothing that stops me from having gauge-broken internal processes if ultimately I can make the S-matrix gauge-invariant. Therefore, the word "physical" should almost always give you a picture of external on-shell gauge-invariant quantities.
So yes, gauge redundancy kills one degree of freedom, and when we are talking about propagating physical degrees of freedom, one more is killed on-shell. You have to understand how that happens. It is not that every time you see an equation of motion, a degree of freedom is killed. Killing of degrees of freedom requires an elaborate process of imposing constraints on the equation of motion known as gauge-fixing. And this has to be done on a case by case basis.
For example, consider the four equations of motion (separated into temporal and spatial sets) for the massless photon $A^\mu = (\phi, \vec A)$ describing four on-shell degrees of freedom as follows.
\begin{align*}
-\Delta \phi + \partial_t \vec\nabla\cdot\vec A = 0\,,\\
\square \vec A - \vec\nabla(\partial_t\phi-\vec\nabla\cdot\vec A) = 0\,.\\
\end{align*}
Since these equations exhibit a gauge symmetry $A_\mu \to A'_\mu := A_\mu + \partial_\mu \alpha_1(x)$, we can try to fix the gauge by choosing $\alpha_1$ such that, for instance, it is a solution of $\square \alpha_1 = -\vec\nabla\cdot\vec A$, giving us
\begin{align*}
\Delta \phi' = 0\,, \\
\square \vec A' - \vec\nabla\partial_t\phi' = 0\,. \\
\\
\vec\nabla\cdot\vec{A}'=0\,.\\
\end{align*}
We have selected a divergence-free field, the so-called Coulomb gauge. Under this choice, the electric potential becomes non-propagating, that is there are no kinetic terms in the Lagrangian for it (observe that $\Delta \phi' = 0$ does not have any time derivatives).
In momentum space, this gauge condition reads $\vec p \cdot \vec \epsilon = 0$ where $ \vec \epsilon$ is the polarisation vector (Fourier transform of the magnetic potential). There are three solutions to this constraint. Choosing a frame in which $p^\mu = (E,0,0,E)$, we find that the three polarisation vectors are
$$ \epsilon^\mu_1 = (0,1,0,0), \qquad \epsilon_2^\mu=(0,0,1,0), \qquad \epsilon_t^\mu = (1,0,0,0) $$
The third polarisation is time-like and therefore cannot be normalized. It is unphysical, and we have to get rid of it. Luckily, the gauge symmetry is not exhausted. There are more available choices of gauge transformations which preserve the Coulomb gauge $\vec p \cdot \vec \epsilon = 0$. For example, we could go from $A'_\mu \to A_\mu:= A'_\mu + \partial_\mu \alpha_2(x)$ such that $\Delta \alpha_2 = 0,\ \partial_t \alpha_2 = - \phi'$ which preserves the divergence and sets $\phi = 0$.
Note that this time we have to make sure that this gauge transformation happens on-shell, namely that $\Delta \phi = 0$, otherwise this gauge-fixing will be inconsistent because $\Delta \alpha_2 = 0 \Rightarrow$ $0 = \Delta \partial_t\alpha_2 = - \Delta\phi' \ne 0$ off-shell. In other words, requiring $\phi = 0$, or equivalently $\epsilon^0 = 0$, in order to get rid of unphysical degrees of freedom requires us to be on-shell.
To summarize, we made an off-shell gauge choice $\vec p \cdot \vec \epsilon = 0$, an on-shell gauge choice $\epsilon^0 = 0$ and our equation of motion became $p^2 = 0$. Having exhausted our gauge choices, we find only two physical polarization modes or degrees of freedom.
Now, you understand that merely having an equation of motion does not eat up a degree of freedom. To find the correct number of degrees of freedom, keep on making gauge choices (producing independent constraint equations), some off-shell and some on-shell, until you exhaust your gauge freedom. Then check how many degrees of freedom you are left with. If you notice any unphysical guy showing up, most likely you haven't used up all your gauge freedom and you still have enough flex to shoot this guy dead. Then, count all that you are left with. That's your answer.
Best Answer
In the Lorenz 'gauge', we have
$$\Box A^{\mu} = \mu_0j^{\mu}$$
If $A^{\mu}$ is a solution, then so is $A^{\mu} + N\epsilon^{\mu}e^{-ik\cdot x}$ if
$$\Box (N\epsilon^{\mu}e^{-ik\cdot x}) = 0$$
Consistency with the Lorenz condition
$$\partial_{\mu}A^{\mu}=0$$
requires
$$k \cdot \epsilon = 0 $$
and consistency with the equation of motion requires that
$$k^2 = k \cdot k = 0$$
But this means that if a polarization four-vector $\epsilon$ satisfies the condition
$$k \cdot \epsilon = 0$$
then $\epsilon' = \epsilon + \alpha k$ also satisfies this condition
$$k \cdot \epsilon' = k \cdot (\epsilon + \alpha k) = k \cdot \epsilon + \alpha k^2 = 0$$
This means we can choose an $\epsilon^{\mu}$ such that $\epsilon^0 = 0$ and then the Lorenz condition implies that the wave and polarization 3-vectors are orthogonal
$$\vec k \cdot \vec\epsilon = 0$$
so there are only two independent polarization vectors (for freely propagating wave solutions).
To summarize, the Lorenz condition implies that the wave and polarization four-vectors are (Minkowski) orthogonal leaving three polarization degrees of freedom.
The equation of motion implies that the wave four-vector is null. Since null-vectors are self-orthogonal ($k^2 = 0$), we are left with two physical polarization degrees of freedom.