Raphael Robinson, in a paper entitled Arithmetical Definitions in the Ring of Integers, gives a definition of $\mathbb{N}$ in $\mathbb{Z}$ using only two existential quantifiers. He does not use Lagrange's Theorem, but he does use the fact that the equation $y^2-az^2=1$ has infinitely many solutions $y$ and $z$ whenever $a$ is a positive nonsquare integer. Whether this is "easier" than Lagrange's Theorem is debatable.
Robinson proves that $x\in \mathbb{N}$ if and only if $$\exists y\exists z \left(x=y^2\vee (y^2=1+xz^2\wedge y^3\ne y)\right).$$
He also proves that no definition using just one existential quantifier is possible.
