Your approach works fine, just start with negative first moment of time:

\begin{equation}
\sup_{x \in \mathbb{R}^{n}}| \nabla_{x} u(t,x)| \leq \frac{C}{\sqrt{T}} \sup_{x \in \mathbb{R}^{n}} |u(t-T,x)| ,\quad t\le 0,\  T>0.
\end{equation}