Are gauge choices in electrodynamics really always possible?

The correct Gauge transformation formula should be $$\begin{aligned} \mathbf A &\mapsto \mathbf A + \nabla \lambda \\ \mathbf V &\mapsto V - \frac{\partial\lambda}{\partial t}, \end{aligned} $$ not something with "gradL/dt". The Coulomb gauge requires $\nabla\cdot\mathbf A=0$, not "rotA = 0". The Lorenz gauge requires $\nabla\cdot\mathbf A + \frac1{c^2}\frac{\partial V}{\partial t}=0$, not "gradA+1/c^2 dV/dt".

The Coulomb gauge can be chosen by solving the Poisson equation $$ \nabla^2 \lambda = -\nabla\cdot\mathbf A$$

The Lorenz gauge can be chosen by solving the inhomogeneous wave equation $$ \nabla^2 \lambda - \frac1{c^2}\frac{\partial^2\lambda}{\partial t^2} = -\nabla\cdot\mathbf{A} - \frac1{c^2}\frac{\partial{V}}{\partial{t}}$$

(Substitute the transformed potentials into the conditions to get the PDEs)

Existence of solutions of these PDEs are guaranteed as long as the source terms (stuff on the RHS) are "well-behaved" (e.g. $\nabla\cdot\mathbf A$ should grow slower than $1/r$ in the Poisson equation)

I'm not sure i understood your question. Look, all E&M Lagrangians have gauge freedom "built in", in the sense that you can re-write the $E$ and $B$ fields and the Lagrangian won't change. Therefore, it's always possible for you to make a choice of gauge, you always have that freedom.

On a slightly tangential note, remember what Helmholtz theorem has to say: you can always decompose a "well behaved" vector field into a sum of a curl and a grad part. And this is exactly what you're doing to the $E$ and $B$ fields in Maxwell's eqs. So, now your question becomes: what happens when you apply your gauge transformation in this context? That is, what is $\nabla\times\nabla$ and $\nabla\cdot\nabla$? What does this imply for $A$ (what equation you get for the vector-potential)?

This should get you going...