Maxwell's equations can be seen as two dynamical equations (the two curl equations), and two constraint equations (the two divergence equations).
So we have 6 unknowns ($E_x,E_y,E_z,B_x,B_y,B_z$).
The two dynamical equations give 6 differential equations.
So we have 6 unknowns, 6 differential equations, but only 2 constraint equations.
So that leaves 4 degrees of freedom.
How do we get a unique solution with 4 degrees of freedom?
Maxwell equations read $$\nabla\cdot \vec E=\rho\tag1$$ $$\nabla\times \vec E = -\frac{\partial \vec B}{\partial t}\tag2$$ $$\nabla\cdot\vec B=0\tag3$$ $$\nabla\times\vec B=\vec j+\frac{\partial\vec E}{\partial t}\tag4$$ For the sake of simplicity, I assume $\vec{j}=0$. Equations (2) and (4) form a linear first order system $$D_x {\bf X}(t,x) = \partial_t {\bf X}(t,x)\tag 5$$ where $${\bf X} = (\vec{E}, \vec{B})^t$$ is a vector in $\mathbb R^6$. $D_x$ is a first order differential operator acting only on the spatial variable $x$: $$D_x = (\nabla \times, \nabla\times)^t S$$ and $S$ is the matrix $6\times 6$ decomposed into 4 blocks made of $3\times 3$ matrices: $I$ and $-I$ on the anti diagonal and $0$, $0$ on the principal diagonal.
As soon as you fix initial conditions $\vec{E}(0,x)$, $\vec{B}(0,x)$, that is ${\bf X}(0,x)$, there is a unique solution of (5). This is true under suitable regularity conditions. This is $${\bf X}(t, x) = e^{tD_x}{\bf X}(0,x)\tag 6$$ We have obtained that (2) and (4) always admit unique solutions for fixed initial conditions (the case $\vec{j}\neq 0$ is a little complication of our simplified case). What about (1) and (3)? It is known that (2) and (4) together with the charge conservation law give rise to $$\partial_t(\nabla\cdot \vec E-\rho)=0$$ and $$\partial_t(\nabla\cdot\vec B)=0$$ where the fields $\vec{E}$ and $\vec{B}$ solve (2) and (4). Therefore, if the initial conditions for (2) and (4) satisfy (1) and (3) (and we are free to fix initial conditions with this feature), these constraints are valid for all times.
ADDENDUM. In case $\vec{j}$ is present, the general solution of (2) and (4) is the sum of the general solution of the homogeneous equation (5) added to a particular solution of (2)-(4). In practice $${\bf X}(t,x) = e^{tD_x} {\bf Y}(x) + e^{tD_x} \int_0^{t} e^{-\tau D_x} {\bf J}(\tau,x) d\tau$$ with ${\bf J}= (\vec{j}(t,x),\vec{0})^t$. It is clear that ${\bf Y}(x)= {\bf X}(0,x)$ again.
The Maxwell's equations are the basics of EM phenomenon. Whatever be the fields you select, they shouldn't violate these fundamental 4 equations. Suppose we are provided a problem to find the electric and magnetic fields of an EM wave or a charge, or whatever be it. As you said, we have now a four component problem. But the degree of freedom is not 4 as each component of E is related to each component of B (Take Faraday's law for example).
Your question has a point. The uniqueness of the solution corresponds to finding the field values of the wave. You should note that the E and B fields are not independent. They are mutually dependent. Once you have E (the electric field components), you could predict the value of B as both are related by the velocity of the wave through that medium under concern. So it is not possible to treat E and B on different perspective. That's against the Maxwell's equations.
So all you need is to know either B or E. Then there is only one degree of freedom even though the problem is still 4 component one.
Lets look at the 4 equations in ED, $$\nabla\cdot \vec E=\rho\tag1$$ $$\nabla\times \vec E = -\frac{\partial \vec B}{\partial t}\tag2$$ $$\nabla\cdot\vec B=0\tag3$$ $$\nabla\times\vec B=\vec j+\frac{\partial\vec E}{\partial t}\tag4$$ which can ofcourse be written in a more compacted form, $$\partial_\mu F^{\mu\nu}=j^\nu \tag5$$
The $(2)$ and the $(3)$ equation actually is my constraint equations. There are 4 constraints - $(2)$ is a vector equations so $3$ constraints plus the $1$ from the scalar equation $(2)$. So we have $2$ degrees of freedom from the $6$ initially.
$$(3)\implies \vec B = \nabla\times\vec A\tag6$$ $$(2)\implies \vec E=-\nabla \phi - \frac{\partial\vec A}{\partial t} \tag7$$
Notice that I can do a gauge transformation such that,
$$\vec A\rightarrow \vec A + \nabla f(\vec x,t)\tag8$$ $$\phi \rightarrow \phi-\frac{\partial f(\vec x,t)}{\partial t}\tag9$$
and my $\vec E$ and $\vec B$ which are the real measurable quantities remains unchanged. So, $\vec A$ and $\phi$ are not $\textbf{unique}$.
