You can't literally solve for $\vec E$ because you could, for instance, add any constant vector field to $\vec E$ and get the same $\vec \nabla \times \vec E.$ So you just don't have enough information unless you know a lot more about the electric field.
So you're right in the sense that you either need symmetry or you need boundary conditions. But while that might seem impossible, consider the similar situation where you have a constant $\vec J$ inside a wire and zero current outside the wire.
If you are comfortable with the magnetic field going in a circle when solving $\vec \nabla \times \vec B = \mu_0 \vec J$ then you should be equally happy with solving $\vec \nabla \times \vec E = - \frac{\partial \vec B}{\partial t}.$ Same techniques work for the same reasons (take a derivative of $\vec B$ slap a minus sign on it and treat it like $\mu_0\vec J$ and call the result an electric field instead of a magnetic field, but nothing changed).
Anything that bothers you in that situation should have bothered you for the equivalent problem with the uniform current through a wire.
If it helps, electromagnetic fields are real things in their own right, they have their own energy and momentum. They can be created and destroyed like anything else and their energy and momentum and move around.
So in a sense the electric fields are just there as things in their own rights and Maxwell really just tells the fields how to change, so $-\vec \nabla \times \vec E$ tells the magnetic field how to change, so you are just find one electric field of many that can make the magnetic field change the way you've been told it should change. Seems less mysterious that there are many possibilities then.
And for symmetry the same thing happens for electric fields. $\frac{1}{\epsilon_0}\left(\frac{1}{\mu_0} \vec \nabla \times \vec B-\vec J\right)$ tells the electric field how to change and since $\vec B$ and $\vec J$ are real things then the electric field has a boss that tells it what to do.
With particles they can have a charge and a mass and a position and a velocity but then they have a boss called a force that tells it how to accelerate. For electromagnetic fields they can have their own values but have no freedom about how to change just like particles have no freedom how about to accelerate.
So your situation is counter intuitive simply because there are multiple electric fields that can make the magnetic field be forced to change that way.
Best Answer
As pointed out by Sebastian Riese in the comments, this follows from Maxwell's equations, and specifically Faraday's Law. Suppose $\vec{B}$ and $\vec{E}$ are plane-polarized plane waves traveling in the same direction with the same frequency: $$ \vec{E} = \vec{E}_0 \cos \left[ \vec{k} \cdot \vec{r} - \omega t\right]\\ \vec{B} = \vec{B}_0 \cos \left[ \vec{k} \cdot \vec{r} - \omega t\right] $$ where $\vec{E}_0 = E_{0x} \hat{\imath} + E_{0y} \hat{\jmath} + E_{0z} \hat{k}$ is a constant vector, and $\vec{B}_0$ is defined similarly. If you write out the $x$-, $y$-, and $z$-components of Faraday's Law $\vec{\nabla} \times \vec{E} = - \partial \vec{B}/\partial t$, you will find that the components of the vectors must satisfy $$ \omega B_{0x} = k_y E_{0z} - k_z E_{0y} \\ \omega B_{0y} = k_z E_{0x} - k_x E_{0z} \\ \omega B_{0x} = k_x E_{0y} - k_y E_{0x} $$ which can be summarized by the equation $\omega \vec{B}_0 = \vec{k} \times \vec{E}$.
You can also apply the other three of Maxwell's equations to the above solution to find out other information about $\vec{E}_0$, $\vec{B}_0$, and $\vec{k}$. Specifically, Gauss's Laws for electric fields and for magnetic fields yield $$ \vec{k} \cdot \vec{E}_0 = \vec{k} \cdot \vec{B}_0 = 0 $$ while Ampere's Law yields $$ \frac{\omega}{c^2} \vec{E}_0 = - \vec{k} \times \vec{B}_0. $$