It's doubtful there are explicit formulas as you write them. Nevertheless, using tangent half angle formulas:
$$\cos x=\dfrac{1-t^2}{1+t^2}, \ \ \sin x = \dfrac{2t}{1+t^2}, \ \ \tan x=\dfrac{2t}{1-t^2}$$
$$\cos y=\dfrac{1-u^2}{1+u^2}, \ \ \sin y = \dfrac{2u}{1+u^2}, \ \ \tan y=\dfrac{2u}{1-u^2}$$
with $t=\tan \tfrac{x}{2} \ \text{and} \ \ u=\tan \tfrac{y}{2}$, you have a method of attack providing solutions in (most) trigonometric equations.
Indeed, with these formulas, the given system:
$$\begin{cases}\cos \alpha & =& \cos \theta \cos x + \sin \theta \sin x \cos y\\
\tan \beta & = & \dfrac{\cos x +\cos \theta \cos \alpha}{\sin \theta \sin x \sin y}\end{cases}$$
becomes, with evident notations:
$$\begin{cases}C_1 & = & C_3 \dfrac{1-t^2}{1+t^2}+S_3\dfrac{2t}{1+t^2} \dfrac{1-u^2}{1+u^2}\\
T_2 & = & \dfrac{\dfrac{1-t^2}{1+t^2} +C_3 C_1}{S_3 \dfrac{2t}{1+t^2} \dfrac{2u}{1+u^2}}\end{cases}$$
In this way, your issue is brought back to the intersection between 2 curves with (in general) 4th degree polynomial equations:
$$\begin{cases}S_3 2t(1-u^2)& = &(1+u^2)(C_1(1+t^2)-C_3(1-t^2)) \ \ \ & (a)\\4T_2S_3tu & = & (1+u^2)((1-t^2)+C_1C_3 (1+t^2)) \ \ \ & (b)\end{cases}\tag{1}$$
which can have at most $4 \times 4 = 16 $ real solutions $(t_k,u_k)$.
Here is a case with 4 solutions (corresponding to case $\alpha=\theta=\pi/4$ and $\beta=$arctan $2$): the curve in blue (resp. in red) has equation (a) (resp. (b)) in (1);
($t$ on abscissas and $u$ on the ordinates) giving, for the indicated root, $t=0.5782=\tan \dfrac{x}{2} \implies x=1.0485 $ radians and the same thing for $u=0.5164 =\tan \dfrac{y}{2} \implies y=0.9534 $ radians.

Edit: An afterthought after having seen the elegant solution by Claude Leibovici.
I didn't notice at first that equations (1) (a) and (b) are separable under the form:
$$\begin{cases}\dfrac{1-u^2}{1+u^2}& = &\dfrac{C_1(1+t^2)-C_3(1-t^2)}{S_3 2t} \ \ \ & (a)\\ \dfrac{2u}{1+u^2} & = & \dfrac{(1-t^2)+C_1C_3 (1+t^2)} {2T_2S_3t}\ \ \ & (b)\end{cases}\tag{2}$$
where we recognize in the two LHS $\cos y$ and $\sin y$ resp. Expressing that $\cos^2 y+\sin^2 y=1$ gives the same kind of fourth degree equation for $t$ as Claude has found...