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
To be sure, this isn't a calculation of potential difference (since the value is path dependent) but is instead the work associated with moving a unit test charge along the path.
The flux rule is simply that the line integral of the electric field along a closed path equals the negative time rate of change of magnetic flux through the surface bounded by the path.
$$\oint_{\partial \Sigma} \mathbf{E} \cdot d\boldsymbol{\ell} = - \frac{d}{dt} \int_{\Sigma} \mathbf{B} \cdot d\mathbf{A}$$
(We assume the path is not changing with time). The area of the triangle is
$$A = \frac{\sqrt{3}}{4}R^2$$
and, I assume, $\vec B$ is out of the page thus
$$\oint_{\partial \Sigma} \mathbf{E} \cdot d\boldsymbol{\ell} = -\frac{B_0}{T}\,A = -\frac{B_0}{T}\frac{\sqrt{3}}{4}R^2$$
Now, remember that this is over the triangular closed path. However, you've already determined that the line integral along the segments $OA$ and $BO$ give zero so the result is due only to the line segment $AB$.
Note that if you had taken the integral along the circular arc from $A$ to $B$ instead of the line segment, the result would be larger and equal to
$$\oint_{\partial \Sigma} \mathbf{E} \cdot d\boldsymbol{\ell} = - \frac{B_0}{T}\frac{\pi R^2}{6}$$