Is the time evolution of physical fields unambiguous without fixing a gauge? Context The origin of the question below stems from this lecture here by Raman Sundrum between $48.20$ to $51$ minutes.

Let at some initial instant $t_0$, the electric and magnetic fields (E and B) are such that they can be derived from an initial field configuration of the four-potential $A^{(1)}_\mu(t_0,{\bf x})$. Obviously, this initial configuration is not unique; it is one of the infinitely many possible choices. However, having chosen this configuration as the initial condition, is it possible to solve for the equation of motion $$\frac{\partial}{\partial t}(\nabla\cdot{\bf A})+\nabla^2\phi=\frac{\rho}{\epsilon_0},\\ \nabla\Big(\frac{1}{c^2}\frac{\partial\phi}{\partial t}+\nabla\cdot{\bf A}\Big)+\frac{1}{c^2}\frac{\partial^2{\bf A}}{\partial t^2}-\nabla^2{\bf A}=\mu_0{\bf J}\tag{1}$$ to unambiguously determine ${\bf E}(t,{\bf x})$ and ${\bf B}(t,{\bf x})$ fields without fixing a gauge? If not, why? If necessary, one may consider vacuum i.e. $\rho={\bf J}=0$ to answer my question.
If the answer to the above question is 'yes', then I have the following question. Suppose instead of choosing $A^{(1)}_\mu(t_0,{\bf x})$, we choose a gauge-transformed four-potential $$A_\mu^{(2)}(t_0,{\bf x})=A^{(1)}_\mu(t_0,{\bf x})+\partial_\mu\theta({\bf x})\tag{2}$$ as the  initial condition. This is a valid initial condition, too. Now, we again solve $(1)$ but this time with the initial condition $A_\mu^{(2)}(t_0,{\bf x})$. Are we gurranteed to obtain the same ${\bf E}(t,{\bf x})$ and ${\bf B}(t,{\bf x})$ as obtained with the previous initial condition?
Question In a nutshell, my question can be summarized as follows.
Without fixing a gauge, and starting with two different initial conditions, if we can solve $\Box A_\mu=0$, are we guaranteed to obtain the same physical fields ${\bf E}(t,{\bf x})$ and ${\bf B}(t,{\bf x})$ at time $t$? 
In other words, if $A_\mu^{(1)}(t_0,{\bf x})$ and $A^{(2)}_\mu(t_0,{\bf x})$ both give the same ${\bf E}, {\bf B}$ at $t_0$, then can we say that $A_\mu^{(1)}(t,{\bf x})$ and $A^{(2)}_\mu(t,{\bf x})$ also give same ${\bf E}, {\bf B}$ at a later time $t>t_0$?
 A: In terms of gauge invariant objects we have 
$$
\frac{\partial {\bf B}}{\partial t} = -{\rm curl}\,{\bf E}\\
\epsilon_0\frac{\partial {\bf E}}{\partial t} =-{\bf J}+\frac 1 {\mu_0} {\rm curl}{\bf B}.
$$
These six equations determine the evolution of ${\bf E}({\bf x},t)$ and ${\bf B}({\bf x},t)$ from ${\bf E}({\bf x},0)$ and ${\bf B}({\bf x},0)$  uniquely without gauge fixing. Further, if 
$$
{\rm div}{\bf B}=0, \quad {\rm div} {\bf E}= \rho/\epsilon_0 
$$ at $t=0$, and provided that $\partial_t \rho+ {\rm div} {\bf J}=0$ then
these conditions are preserved at all times. There is no need to introduce the potential $A^\mu$. 
A: You seem to have multiple questions here.

Is it possible to solve the equations of motion to unambiguously determine $\mathbf E(\mathbf x,t)$ and $\mathbf B(\mathbf x,t)$ without choosing a gauge?

Yes, certainly.  It's not difficult to rearrange Maxwell's equations to yield
$$\left(\nabla^2 - \frac{1}{c^2}\frac{\partial^2}{\partial t^2}\right)\left.\cases{\mathbf E \\ 
\mathbf B}\right\} = \left.\cases{\frac{1}{\epsilon_0}\nabla \rho +\mu_0 \frac{\partial}{\partial t}\mathbf J\\-\mu_0\nabla\times\mathbf J}\right\}$$
Therefore the $\mathbf E$ and $\mathbf B$ terms are solutions to the inhomogeneous wave equation, with sources terms involving $\rho$ and  $\mathbf J$.  If the latter are prescribed and valid initial/boundary conditions are applied, then $\mathbf E$ and $\mathbf B$ can be immediately written down e.g. via Green's functions. 

If $A_\mu^{(1)}(t_0,{\bf x})$ and $A^{(2)}_\mu(t_0,{\bf x})$ both give the same ${\bf E}, {\bf B}$ at $t_0$, then can we say that $A_\mu^{(1)}(t,{\bf x})$ and $A^{(2)}_\mu(t,{\bf x})$ also give same ${\bf E}, {\bf B}$ at a later time $t>t_0$?

Yes, this is also true (of course it must be - otherwise it would matter which gauge we chose at time $t=t_0$, and so there wouldn't actually be any gauge freedom at all). 

As clarified by your comment, the question you're trying to ask is actually the following:

If $A_\mu^{(1)}(t_0,{\bf x})= A^{(2)}_\mu(t_0,{\bf x})$ and $\dot A_\mu^{(1)}(t_0,{\bf x})= \dot A^{(2)}_\mu(t_0,{\bf x})$ at $t_0$, then is $A^{(1)}_\mu(t,\mathbf x) = A^{(2)}_\mu(t,\mathbf x)$ for all $t$?

The answer to this question is an emphatic no.  Specifying the 4-potential $A_\mu$ and its derivatives at some initial moment is not sufficient to determine it for all $t$, and so it does not correspond to a well-posed initial value problem.
That being said, we are rescued by the answer to your question above.  While there is an entire family of $A_\mu$'s which have precisely the same initial conditions (making the IVP ill-defined), every member of that family yields precisely the same $\mathbf E$ and $\mathbf B$. In other words, the ambiguity in the time evolution of $A_\mu$ is the introduction of a (physically irrelevant) time-varying gauge transformation.
A: So, the thing is that the equations (1) along with the initial condition $A^{(1)}_\mu(t_0,\vec{x})$ do not admit a unique solution. Namely, if you have a solution $A(t,\vec{x})$, then $A(t,\vec{x})+\partial_\mu\theta(t,\vec{x})$, for some $\theta$ whose support does not overlap with the time slice $t=t_0$. The key point is that the latter also satisfies the same initial condition. 
For your second question, you have to be careful because Maxwell's equations are not $\square A_\mu=j_\mu$. They are $\square A_\mu-\partial_\mu(\partial\cdot A)=j_\mu$. Everything is however clearer in the language of differential forms. In it, the equations of motion  are $d\star dA=J$. However, $F=dA$ and thus, these are really equations $d\star F=J$ for $F$. The later can be shown to have a unique solution given initial conditions.
Summary The equations $d\star dA=J$ with a given initial condition cannot be solved, in the sense that solutions are not unique. The equations $d\star F=J$ can however. In particular, two solutions $A^{(1)}$ and $A^{(2)}$ of the former leading to the same initial $F$ have to lead to the same $F$ at later times.
