First, note that, strictly speaking, there is no such thing as spontaneous symmetry breaking in Higgs mechanism. I mean, that below and under the Higgs scale (i.e., at scale, at which non-zero Higgs VEV appears) the lagrangian can be rewritten in a gauge invariant way. How is it possible? The answer is that there are different physical states (i.e., eigenstates of hamiltonian) below and under the Higgs scale. Under the Higgs scale eigenstates of hamiltonian form also representations of the gauge group. But below it eigenstates of hamiltonian don't form representations of the gauge group. These eigenstates are linear combination of transverse and longitudinal degrees of freedom.
So, in some sence, nothing happens with three scalar fields in Higgs doublet. They just don't appear as physical states below the Higgs scale.
However, I was under the impression that gauge invariance is not a
true physical symmetry, but rather a redundancy in description of a
given physical theory?!
This is true. Instead of the symmetry transformation
$$
U|\Psi\rangle \to |\Psi'\rangle
$$
the unitary gauge transformation operator $U$ with the generator $G$ acts on physical state $|\Psi\rangle$ as
$$
\tag 1 U(G)|\Psi\rangle = |\Psi\rangle \leftrightarrow G(\mathbf x)|\Psi\rangle = 0
$$
Analogically, in theory with interactions there is another "do-nothing transformation", called the Ward identity. It states that any amplitude $M$ with at least one external photon line, i.e., $M = M_{\mu}\epsilon^{\mu}(p)$, is transversal:
$$
\tag 2 p^{\mu}M_{\mu} = 0
$$
It is the analog of gauge current conservation in the classical theory.
Together, $(1)$ and $(2)$ can be called as "the gauge invariance of the quantum field theory", but in fact they are just the description of the gauge redundancy.
It turns out that typically $(2)$ forbids the mass of the photon. Precisely, it can be shown that in most cases it prevents the position of the photon propagator pole (which defines its mass) to be shifted from zero.
However, in some particular cases we can write down the gauge field mass without violating the gauge invariance (this statement in fact is not exact, see below, however typically people say it as "mantra").
Really, classically one can write down the gauge-invariant field
$$
\tag 3 V_{\mu} = A_{\mu} - \partial_{\mu}\frac{1}{\square}\partial_{\nu}A^{\nu}
$$
Corresponding mass term $m^{2}V_{\mu}V^{\mu}$ doesn't violate the gauge invariance, although it looks cumbersome. The second summand in $(3)$ looks bad, but the situation becomes good when there is some scalar degree of freedom $\varphi$ which parametrizes it:
$$
\frac{1}{\square}\partial_{\nu}A^{\nu} \to \varphi
$$
In the quantum field theory corresponding situation appears when the photon vacuum polarization amplitude has the pole at zero momentum.
There are few models in which such situation appears. The first one is the model with the Higgs mechanism (often called "spontaneous breaking" of the gauge symmetry), where the particles spectrum doesn't form the representation of the gauge group below some scale $\Lambda$. Instead of $A_{\mu}$ we're dealing with $V_{\mu}$; people say that $A_{\mu}$ eats the "Goldstone boson" $\varphi$. But note that in fact $V_{\mu}$ is not the "photon"; it is the combination of the photon and longitudinal polarization.
The prototype of this idea is the classical theory of EM field interacting with the plasma (this was pioneered by Anderson).
The second example is strong interaction regime bozonization. It happens in Schwinger's massless 2D QED. In this case, two massless fermions form the massless bound state shifting the photon propagator pole. One can't write down the local term generating the photon mass without introducing the new field representing this bound state.
Best Answer
Let me anwser a closely related quenstion: Consider a U(1) gauge theory with massless gauge bosons, can any small perturbations give the gauge boson an mass.
Amazingly, the anser is NO. The masslessness of the gauge boson is topologically robust. No small perturbations can give the gauge boson an mass. For detail, see my article.
Let me make the statement more precise. Here we consider a compact U(1) gauge theory with a finite UV cutoff (such as a lattice gauge theory), that contains gapless gauge bosons at low energies. Then no small perturbations to this compact U(1) gauge theory with a finite UV cutoff can give the gauge boson an mass, even for the small perturbations that break the gauge invariance.
So the masslessness of gauge boson is a stable universal property of a quantum phase. Only a phase transition can make the gauge boson massive.