$\newcommand{\tY}{\tilde Y}\newcommand{\F}{\mathcal F}\newcommand{\Om}{\Omega}$As stated above, the answer to the question is yes, and we can even replace the condition "$Z\ge X$ $P$-almost surely" simply by "$Z\ge X$".
Indeed, let $A:=X^{-1}((-\infty,0))$ and $B:=Y^{-1}((-\infty,0))$. Then $P(A)=P(X<0)>0$ and $P(B)=P(Y<0)>0$. If $P(A\cap B)>0$, then we can just let $Z:=\max(X,Y)$.
Suppose now that $P(A\cap B)=0$. Then, by Sierpinski's theorem, we can find a real number $p>0$ and sets $C$ and $D$ in $\F$ such that
\begin{equation*}
C\subseteq A,\quad D\subseteq B,\quad C\cap D=\emptyset,\quad P(C)=P(D)=p.
\end{equation*}
For $F\in\F$, let
\begin{equation*}
P_D(F):=P(F|D)=\frac{P(F\cap D)}p.
\end{equation*}
Then $P_D$ is a non-atomic probability measure on the measurable space $(\Om,\F)$ such that $P_D(D)=1$.
So, as shown in this previous answer, there exists a r.v. $U_D$ on the probability space $(\Om,\F,P_D)$ that is uniformly distributed on the interval $(0,1)$.
Similarly defined are the non-atomic probability measure $P_C$ and a r.v. $U_C$.
For each real $y$, let
\begin{equation*}
F_{Y|D}(y):=P(Y\le y|D)=\frac{P(Y^{-1}((-\infty,y])\cap D)}p,
\end{equation*}
so that $F_{Y|D}$ is the c.d.f. of the conditional distribution of $Y$ over $D$.
Next, let
\begin{equation*}
Y_{D,C}:=F_{Y|D}^{-1}(U_C),
\end{equation*}
where
\begin{equation*}
F^{-1}(u):=\inf\{x\in\Bbb R\colon F(x)\ge u\}
\end{equation*}
for any c.d.f. $F$ and any $u\in(0,1)$. Then the c.d.f. of the distribution of the r.v. $Y_{D,C}$ wrt the probability measure $P_C$ is $F_{Y|D}$. So, for each Borel set $E\subseteq\Bbb R$,
\begin{equation*}
\frac{P(Y_{D,C}^{-1}(E)\cap C)}p=P_C(Y_{D,C}^{-1}(E))
=\frac{P(Y^{-1}(E)\cap D)}p,
\end{equation*}
so that
\begin{equation*}
P(Y_{D,C}^{-1}(E)\cap C)=P(Y^{-1}(E)\cap D). \tag{10}\label{10}
\end{equation*}
Similarly, for each Borel set $E\subseteq\Bbb R$,
\begin{equation*}
P(Y_{C,D}^{-1}(E)\cap D)=P(Y^{-1}(E)\cap C), \tag{20}\label{20}
\end{equation*}
where the r.v. $Y_{C,D}$ is defined similarly to $Y_{D,C}$.
Let now
\begin{equation*}
\tY:=Y_{D,C}\,1_C+Y_{C,D}\,1_D+Y_{D,C}\,1_{\Om\setminus C\setminus D}.
\end{equation*}
Then, in view of \eqref{10} and \eqref{20}, for each Borel set $E\subseteq\Bbb R$,
\begin{align*}
&P(\tY^{-1}(E)) \\
&=P(Y_{D,C}^{-1}(E)\cap C)+P(Y_{C,D}^{-1}(E)\cap D)
+P(Y^{-1}(E)\setminus C\setminus D) \\
&=P(Y^{-1}(E)\cap D)+P(Y^{-1}(E)\cap C)
+P(Y^{-1}(E)\setminus C\setminus D) \\
&=P(Y^{-1}(E)),
\end{align*}
so that $\tY$ equals $Y$ in distribution (wrt to $P$).
Let now
\begin{equation*}
Z:=\max(X,\tY).
\end{equation*}
Then $Z\ge X$ and $Z\ge\tY$, so that $Z$ stochastically dominates $\tY$ and therefore stochastically dominates $Y$.
Finally, recalling that $X<0$ on $C$ and using \eqref{10} again, we get
\begin{align*}
P(Z<0)&\ge P(\tY^{-1}((-\infty,0))\cap C) \\
&=P(Y_{D,C}^{-1}((-\infty,0))\cap C) \\
&=P(Y^{-1}((-\infty,0))\cap D) \\
&=P(B\cap D)=P(D)=p>0. \quad\Box
\end{align*}