Yes, there exist such integers $r$ and $s$. It is simplest to use the Fundamental Theorem of Arithmetic (Unique Factorization Theorem). The result is easy to prove for negative $z$ if we know the result holds for positive $z$. Also, the result is clear for $z=1$. So we may assume that $z\gt 1$.
Let $z=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where the $p_i$ are distinct primes. Then $z^3=p_1^{3a_1}\cdots p_k^{3a_k}$.
Because by assumption $x+y$ and $x^2-xy+y^2$ are relatively prime, the primes in the factorization of $z^3$ must split into two sets, the ones that "belong to" $x+y$ and the ones that belong to $x^2-xy+y^2$. Because any prime has exponent divisible by $3$, each of $x+y$ and $x^2-xy+y^2$ is a perfect cube.
The rest is easy. From $z^3=r^3s^3$, it immediately follows that $z=rs$.
Remark: Note that $x$ and $y$ relatively prime does not imply $x+y$ and $x^2-xy+y^2$ are relatively prime. They could be both divisible by $3$.