Well, it seems that this problem has no nice analytic solution, so I've come up with a numerical one.
So, given a set of angles, $\{\alpha, \beta,\gamma,\delta\}$, we want to cosntruct an quadrilateral $ABCD$ with appropriate angles. Construct the diagonal $AD$ and denote the angles as in the picture:

If we obtain $\xi$ and $\eta$, then we will be able to construct the ABCD since we know how to construct triangles (using a method I described in the original post).
Consider the following function:
$$
F(x,y,z) = \dfrac{\cos(x)\cos(y) - \cos(z)}{\sin(x)\sin(y)}
$$
From the hyperbolic law of cosines, it tells hyperbolic cosine of side overlooking angle $z$ in triangle with angles $\{x,y,z\}$. Then for some pair ${(\xi, \eta)}$ to be valid it is neccesarry that
$$
\Phi(\xi, \eta) = F(\xi, \eta, \beta) - F(\alpha - \xi, \gamma -\eta,\delta) =0.
$$
It can be straighforwardly checked that
$$
\dfrac{\partial\Phi(\xi, \eta)}{\partial \xi} < 0,\ \dfrac{\partial\Phi(\xi, \eta)}{\partial \eta} < 0\ \text{for all}\ (\xi, \eta)\in(0,\alpha)\times(0,\gamma).
$$
Also, it is obvious that
$$
\lim\limits_{\eta\to 0}\Phi(\xi, \eta) = +\infty,\ \lim\limits_{\eta\to\gamma }\Phi(\xi, \eta) = -\infty\text{ for all }\xi\in(0,\alpha),
$$
and
$$
\lim\limits_{\xi\to 0}\Phi(\xi, \eta) = +\infty,\ \lim\limits_{\xi\to\alpha }\Phi(\xi, \eta) = -\infty\text{ for all }\eta\in(0,\gamma),
$$
Hence, for all $\xi\in(0,\alpha)$ the equation $\Phi(\xi, \eta)=0$ has a unique solution $\eta^*$, and for all $\eta\in(0,\gamma)$ it has a unique solution $\xi^*$. Moreover, from monotonyty, these equations can be easily numerically solved using, say, bisection method.
So, the algorithm can now be formulated as follows.
- Select a grid of points $\{\xi_0, \xi_1,\ldots, \xi_N\}$ in segment $[\varepsilon, \alpha - \varepsilon]$.
- For a given $\xi_i$, find the root $\eta_i$ of equation $\Phi(\xi_i, \eta) = 0$. Repeat untill $\eta_i\in(0,\gamma)$.
- Construct a triangle $ABC$ with angles $(\xi, \eta,\beta)$.
- Construct a triangle $AD'F$ with angles $(\alpha-\xi, \gamma-\eta, \delta)$ such thath $AF$ is colinear with $AC$.
- Rotate triangle $ADF$ around $A$ by $\xi$ to triangle $ADF'$. Than points $A,B,C,D$ will form the desired quadrilateral.
This method can obviously extended to an arbitrary polygon.