You're almost there. For the symmetry argument: first notice that Faraday's law, $\oint\textbf{E} \cdot d\textbf{l}=-\frac{d\Phi}{dt}$, looks the same as Ampère's law from electrostatics: $\oint\textbf{B}\cdot d\textbf{l}=\mu_0 I$.
Now consider a current (or a homogeneous current density) pointing in the positive $x_3$-direction. What is the direction of the magnetic field such a current would produce? Indeed, using the right-hand rule (or any of your favorite symmetry arguments) it readily follows that the $\textbf{B}$-field encircles the current, i.e. it is symmetric around the $x_3$-axis and points anticlockwise. I trust that you are familiar with symmetries of magnetic fields produced by steady currents.
Now compare the form of Faraday's and Ampère's laws. Because the laws look exactly the same, it's easy to see that the electric field due to a flux decrease in the $x_3$-direction will have the same symmetry as a magnetic field due to a current (density) in the $x_3$ -direction. Hence here the $\bf{E}$-field will also be symmetric around the $x_3$-axis and will point in the azimuthal direction! (It'll point clockwise if the flux increases, but this will follow from the calculation.)
Therefore, we can do the calculation in just the way you did, yielding
$\textbf{E}=-\frac{r}{2}\frac{dB}{dt}\hat{\phi}$ as you noted. (Here $\textbf{B}(t)=B(t) \hat{x}_3$.)
Note that in your calculation you had already assumed that $\textbf{E}$ is in the $\hat{\phi}$ direction when you said that $2\pi r |\vec{E}| = \int_{\gamma} \vec{E} d\vec{s}$, since this assumes that $\bf{E}$ and $d\bf{s}$ are parallel.
The last thing to notice is that your calculation holds when your contour $\gamma$ is in the circle $A$ where the flux changes. Let $R$ be the radius of $A$. If $\gamma$ is outside $A$, then it encloses all of the flux, hence $\frac{d\Phi}{dt}=\pi R^2\frac{dB}{dt}$ so that for $r>R$ we get
$\textbf{E}=-\frac{R^2}{2r}\frac{dB}{dt}\hat{\phi}$,
which nicely vanishes as $r\rightarrow \infty$.
Finally, notice that if we would calculate the magnetic field produced by a volume charge density $\textbf{J}=J_0\hat{x}_3$ with $J_0$ constant, and replaced in our answer $J_0$ by $-\frac{1}{\mu_0}\frac{dB}{dt}$, we'd get exactly the electric field above.
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
You can find a solution on most of space, but not all of space. To see why, imagine taking the flux integral of $\vec{B} = \hat{r}/r^2$ over the surface of a sphere $S$ of radius $r$. Doing this integral is straightforward, and yields $$ \iint_S \vec{B} \cdot d\vec{a} = 4\pi. $$ Now let's assume that there exists a vector field $\vec{A}$ such that $\vec{\nabla} \times \vec{A} = \vec{B}$. This implies that $$ 4\pi = \iint_S (\vec{\nabla} \times \vec{A}) \cdot d\vec{a}. $$ But according to Stokes' theorem, we can always replace the integral of the curl of a vector field over a surface with a line integral around the surface's boundary $\partial S$: $$ \iint_S (\vec{\nabla} \times \vec{A}) \cdot d\vec{a} = \oint_{\partial S} \vec{A} \cdot d\vec{l}. $$ The problem is, of course, that the surface of a sphere has no boundary! This means that $\partial S$ is empty, the integral vanishes, and we conclude that $$ 4\pi = \iint_S (\vec{\nabla} \times \vec{A}) \cdot d\vec{a}= \oint_{\partial S} \vec{A} \cdot d\vec{l} = 0, $$ which is a contradiction.[citation needed]
If you really want to work with a vector potential for a monopole, then, you have to avoid enclosing it in a spherical surface. One well-known way to do this is to "remove" the negative $z$-axis ($\theta = \pi$) from the space you're considering. In that case, $S$ can never be a full sphere; it can only be a sphere minus a tiny "puncture" at the south pole, and the boundary around that puncture means that we no longer necessarily have $\oint_{\partial S} \vec{A} \cdot d\vec{l} = 0$. In particular, if you then define $$ \vec{A} = \frac{1 - \cos \theta}{r \sin\theta} \hat{\phi} = \frac{\tan \frac{\theta}{2}}{r} \hat{\phi}, $$ then it's not hard to show that $\vec{\nabla} \times \vec{A} = \hat{r}/r^2$. As we can see, though, $|\vec{A}| \to \infty$ as $\theta \to \pi$, meaning that this vector potential can't be extended over all of space.