By postulating gauge invariance, you start by assuming that the physics does not depend on the choice of gauge. From there, the physical observables are constructed such as to be gauge invariant. Typically, you try to do it using gauge invariant objects like $F_{\mu\nu}$, but sometimes it is easier to use the potential and then check for gauge invariance.
The choice of the gauge is merely for mathematical convenience. The liberty of the gauge is determined by your equation of gauge transformation. For example, if you start from a potential $A$, you want to know whether you can fix $A_x = 0$. This amounts to choosing $\lambda$ st:
$$
A_x+\partial_x\lambda = 0
$$
So any $\lambda$ of the form:
$$
\lambda = -\int dxA_x+\lambda'
$$
with $\lambda'$ independent of $x$. Therefore, your gauge fixing is possible, but does not fix the potential entirely.
If you try to fix the gauge by setting two components to $0$, then you'll be in trouble already. Say you want $A_x=A_t=0$. You therefore want:
$$
A_x+\partial_x\lambda = A_y+\partial_y\lambda = 0
$$
However, this is only possible for the special fields satisfying:
$$
\partial_x A_y = \partial_yA_x
$$
A counter example for this would be $A=(0,y,-x,0)$. This gauge fixing is therefore not possible for all fields, it's invalid. A fortiori, fixing all the components to $0$ is not admissible either.
Two usual gauge fixing are the Lorentz gauge:
$$
\partial\cdot A = 0
$$
which has the advantage of staying gauge invariant and transforms EM into uncoupled wave equations. However, there is a "leftover degree of freedom" in some sense, and makes quantisation trickier. The other is the Coulomb gauge:
$$
\nabla\cdot \vec A = 0
$$
It is easier to quantise and the potential satisfies the same equations of electrostatic. However you lose relativistic invariance and the vector potential is harder to calculate.
A good way to build intuition is to Fourier space. Gauge invariance says that you can add something proportional to the four-wave vector. This is why in EM, you can restrict to the case of transverse waves.
Btw, classically, the full gauge invariance is rather:
$$
A\to A+B
$$
with $\partial_\mu B_\nu = \partial_\nu B_\mu$. Locally (in a simply connected neighbourhood), you can always find a $\lambda$ such that $B = \partial \lambda$, but this is not true globally. In contrast, gauge invariance in quantum mechanics is more restrictive as is is rather:
$$
A\to A+\partial\lambda
$$
with $\lambda$ defined globally up to an additive integer multiple of the inverse charge.
Hope this helps.
Answer to comment
You can view gauge freedom when you have a finite number of degrees of freedom. Say you want to describe a particle on a sphere subject only to the constraining force. You have two degrees of freedom, which you can keep track of by using an atlas of the sphere (spherical coordinates etc.).
Another way of approaching the problem, which is analogous to gauge freedom, is rather to say that the particle actually lives in 3D. However, since the real particle lives on the sphere you introduced an extra, non-physical degree of freedom (radial direction). All physical quantities will not depend on this extra degree of freedom by definition. However, looking at your new system, its symmetries are enhanced, which gives you more freedom to choose appropriate coordinates.
The analogue of when your gauge fixing is too restrictive would be to define a projection that is not defined for every point of the sphere. You would need to introduce more projections in order to cover the sphere completely.