We need to find a vector potential $\mathbf{A}(\mathbf{x},t)$ such that
\begin{align}
-\frac{\partial \mathbf{A}}{\partial t} &= \mathbf{E}, \tag{1}\label{1} \\
\nabla \times \mathbf{A} &= \mathbf{B} = 0, \tag{2}\label{2}\\
\nabla \cdot \mathbf{A} &= 0, \tag{3}\label{3}\\
\nabla^2 \mathbf{A} - c^2 \frac{\partial^2 \mathbf{A}}{\partial t^2} &= -\mu_0 \mathbf{J} = 0. \tag{4}\label{4}
\end{align}
Equations \eqref{1} and \eqref{2} are simply the electric and magnetic fields in terms of the vector potential (with $\phi(\mathbf{x}) = 0$). \eqref{3} is the gauge condition. \eqref{4} is Maxwell's equation for the vector potential in the Coulomb gauge, again with $\phi(\mathbf{x})=0$.
From \eqref{1} we have that $\mathbf{A}(\mathbf{x},t)$ must be at least linear in $t$, while \eqref{2} and \eqref{3} will be satisfied if $\mathbf{A}(\mathbf{x},t)$ is independent of $\mathbf{x}$. Finally, the second term in \eqref{4} will vanish if $\mathbf{A}(\mathbf{x},t)$ is at most linear in $t$.
Therefore, we can write
$$\mathbf{A}(\mathbf{x},t) = - t \mathbf{E}$$ for the vector potential of a uniform electric field.