Lemma. Let $p$ be a prime number and $a$, $b$, $c \in \mathbb{Z}/p\mathbb{Z}$. Then there exist $x$, $y$, $z \in \mathbb{Z}$ such that $|x|$, $|y|$, $|z| < \sqrt[3]{p}$, $(x, y, z) \neq (0, 0, 0)$ and $ax + by + cz \equiv 0 \pmod{p}$.

Proof. Consider the set $M := \{(x, y, z) : x, y, z \in \{0, 1, \dots, \lfloor \sqrt[3]{p} \rfloor\}\}$. We have that $|M| > p$, i.e. in $M$ there are two distinct elements $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$, for which $ax_1 + by_1 + cz_1 \equiv ax_2 + by_2 + cz_2 \pmod{p}$. Thus $(x_1 - x_2, y_1 - y_2, z_1 - z_2)$ satisfies the conditions of the lemma.

Now let $p \equiv 2 \pmod{3}$. Then the comparison $x^3 \equiv 2 \pmod{p}$ has a solution $a$, since the function $x \mapsto x^3$ is injective in $\mathbb{Z}/p\mathbb{Z}$, hence it is surjective. One way to verify this is to see that $x^3 \equiv 1 \pmod{p}$ has only $1$ for a solution, since $(3, p-1) = 1$ and hence the exponent of $x$ (mod $p$) is $1$.

From the lemma, there exist $x$, $y$, $z$ with $|x|$, $|y|$, $|z| < \sqrt[3]{p}$, for which $x + ay + a^2z \equiv 0 \pmod{p}$. From here we get that $x^3 + a^3y^3 + a^6z^3 - 3a^3xyz \equiv 0 \pmod{p}$. The latter is equivalent to $x^3 + 2y^3 + 4z^3 - 6xyz \equiv 0 \pmod{p}$.

On the other hand $|x|$, $|y|$, $|z| < \sqrt[3]{p}$ gives $|x^3 + 2y^3 + 4z^3 - 6xyz| < 13p$. Also notice that if $x^3 + 2y^3 + 4z^3 - 6xyz < 0$, then the triple $(-x, -y, -z)$ will give a natural number divisible by $p$.

It remains to note that $x^3 + 2y^3 + 4z^3 - 6xyz \neq 0$. Indeed, if $x^3 + 2y^3 + 4z^3 - 6xyz = 0$, then we have $(x + \sqrt[3]{2}y + \sqrt[3]{4}z)((x - \sqrt[3]{2}y)^2 + (x - \sqrt[3]{4}z)^2 + (\sqrt[3]{2}y - \sqrt[3]{4}z)^2) = 0$, i.e. $x = \sqrt[3]{2}y = \sqrt[3]{4}z$ or $x + y\sqrt[3]{2} + z\sqrt[3]{4} = 0$, whose only integer solutions are $(x, y, z) = (0, 0, 0)$ (the first follows because $\sqrt[3]{2}$ is irrational, and the second follows from the fact that $x^3 - 2$ is the minimal polynomial of $\sqrt[3]{2}$ over the rational numbers). $\square$