We can get an algorithm by constructively recasting a standard proof of the transcendence of $e$, and simplifying it since we need only that $e$ is not a root of a rational number. The result may not be the best algorithm, but it makes the time-analysis easy.
Algorithm
To start, we assume without loss of generality that $x_1, x_2, y_1, y_2$ are all integers.
Let $t=x_2-x_1$ and $u=z_1^{y_1}/z_2^{y_2}$, so the question is equivalent to deciding whether $e^t>u$.
Let $u=a/b$, with $a$ and $b$ integers. Choose an odd $p$ with $p>3t^2$ and $2^p>b 3^t t$. (We do not need $p$ to be prime, though it was in the source.)
Then let
$$f(p,t,x)=\frac{x^p(x-t)^p}{p!\ e^x}$$
$$M=\int_0^\infty f(p,t,x) dx$$
$$M_t=e^t \int_t^\infty f(p,t,x) dx$$
$$\epsilon=e^t \int_0^t f(p,t,x) dx$$
Now we are looking to determine whether
\begin{align}
e^t &> u \\
(M_t + \epsilon)/M &> a/b \\
bM_t - aM &> -b \epsilon
\end{align}
where all three expressions are equivalent.
On the left hand side, we can evaluate the integral for $M$ using the identity $\int_0^\infty x^n e^{-x} dx = n!$, and conclude that $M$ is an integer. Using the change of variables $y=x-t$, we conclude that $M_t$ is also an integer, and so is $bM_t - aM$.
On the right hand side, $p>3t^2$ makes $|f(p,t,x)|<1/2^p$, so the second condition on $p$ gives $0<-b\epsilon<1$.
Thus the inequality holds iff $bM_t-aM>0$, and the algorithm is just to compare those as integers.
Time Analysis
The significant time in this algorithm is in calculating $M$ and $M_t$. To calculate $M$, we added $p+1$ summands, each of which is bounded by
$$\frac{(2p)!}{p!}\binom{p}{p/2}t^p < (3pt)^p$$
The time for the algorithm is roughly the time to write out all those summands, which is $O(p^2\log(pt))$ or
$$O(t^4 \log t +(\log b)^2\log\log b)$$
