To make things simpler I assume $\alpha_0=0$ (the desired value of $\alpha_0$ can always be added/subtracted at the end); furthermore I take the equator at $\delta=0$, so the range of the latitude $\delta$ is the interval $[-\pi/2,\pi/2]$. Your change of coordinates amounts to changing the standard basis $(e_1,e_, e_3)$ of ${\mathbb R}^3$ to the new basis
$$\bar e_1=(\cos\delta_0,0,\sin\delta_0), \quad \bar e_2=(0,1,0),\quad \bar e_3=(-\sin\delta_0,0,\cos\delta_0)\ .$$
It follows that the new coordinates $\bar x_k$ are given in terms of the old ones $x_i$ by the formulas
$$\bar x_1=\cos\delta_0 x_1 +\sin\delta_0 x_3, \quad \bar x_2=x_2,\quad \bar x_3=-\sin\delta_0 x_1+\cos\delta_0 x_3\ .$$
Now we have to express this in terms of the "geographical" quantities $\alpha$, $\delta$, resp. $\bar\alpha$, $\bar\delta$. On the one hand we have
$$x_1=\cos\delta\cos\alpha,\quad x_2=\cos\delta\sin\alpha, \quad x_3=\sin\delta\ ,$$
and on the other hand
$$\bar\alpha=\arg\Bigl({\bar x_1\over\rho},{\bar x_2\over\rho}\Bigr), \quad \bar\delta=\arcsin(\bar x_3)\ ,$$
where $\rho:=\sqrt{\bar x_1^2+\bar x_2^2}$. Putting it all together some simplifications will result.
Hint:
The shortest distance between two points on the surface of a sphere is the distance measured on the great-circle between them.
For 1) use the the definition of latitude $\alpha$ as the shortest distance between a point a the equator and note that the distance from the pole and the equator is $\pi/2$.
For 2) find the great circle that pass between the two points.
The two cities and the north pole define a spherical triangle $ANB$ and you know:
$$
A=(\phi_A,\theta_A)\qquad B=(\phi_B,\theta_B) \qquad N=(0,\pi/2)
$$
You can find:
the arcs $AN=b$ and $BN=a$ (as in 1))
the angle in $N$: $\nu=\angle ANB=\theta_B-\theta_A$
the arc distance $AB=n$ between the two points $A$ $B$ given by:
$$
\cos n= \sin \theta_A\sin \theta_B+\cos \theta_A\cos \theta_B\cos(\phi_A-\phi_B)
$$
Now, using the sine rule
$$
\dfrac{\sin a}{\sin \alpha}=\dfrac{\sin b}{\sin \beta}=\dfrac{\sin n}{\sin \nu}
$$
you can solve the triangle finding the angles $\alpha=\angle NAB$ and $\beta=\angle NBA$
The minimum arc distance of the arc $AB$ from $N$ is the arc height $h$ of the triangle, given by:
$$
\dfrac{\sin h}{\sin \alpha}=\dfrac{\sin b}{\sin \pi/2}
$$
Best Answer
Well, I ended up solving this myself after a little more thought. The solution is to convert from the
(r, phi, theta)
of spherical coordinates to the(x, y, z)
of Cartesian coordinates, then swap the z-axis with one of the others before finally converting back to spherical coordinates again.