Showing that Coulomb and Lorenz Gauges are indeed valid Gauge Transformations?

Comment to the question (v1): It seems OP is conflating, on one hand, a gauge transformation

$$ \tilde{A}_{\mu} ~=~ A_{\mu} +d_{\mu}\Lambda $$

with, on the other hand, a gauge-fixing condition, i.e. choosing a gauge, such e.g., Lorenz gauge, Coulomb gauge, axial gauge, temporal gauge, etc.

A gauge transformation can e.g. go between two gauge-fixing conditions. More generally, gauge transformations run along gauge orbits. Ideally a gauge-fixing condition intersects all gauge orbits exactly once.

Mathematically, depending on the topology of spacetime, it is often a non-trivial issue whether such a gauge-fixing condition is globally well-defined and uniquely specifies the gauge-field, cf. e.g. the Gribov problem. Existence and uniqueness of solutions to gauge-fixing conditions is the topic of several Phys.SE posts, see e.g. this and this Phys.SE posts.

The Coulomb and Lorenz gauges are gauge fixing conditions, not gauge transformations. Your question still makes sense, but it should be phrased more like this: how can you prove that for arbitrary $\mathbf A_0$ and $V_0$ there always exists a gauge transformation to fields $\mathbf A$ and $V$ that satisfy these conditions? In fact many such transformations always exist (these conditions don't completely fix the gauge).

For the Coulomb gauge condition, we need $0 = \nabla\cdot\mathbf A = \nabla\cdot(\mathbf A_0 + \nabla\lambda) = \nabla\cdot\mathbf A_0 + \nabla^2 \lambda$. This is Poisson's equation, which can be solved for $\lambda$ with Green's functions. The Lorenz case is easier if you use four-vectors, in which case you get a 3+1 dimensional version of Poisson's equation.