Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's **A Classical Introduction to Modern Number Theory**.

How can I count the relative density of those $p$ (of the form $3k+1$) such that the equation $2=3x^3$ has no solutions modulo $p$?

Really, even pointers on how to say anything meaningful about these $p$ are welcome. Originally I also asked about how to count the density of *all* $p$ (not just those of the form $3k+1$) such that $2$ (or $3$) is not a cubic residue modulo $p$, but Felipe Voloch's comment quickly addresses how to deal with them, via Chebotarev's density theorem.

The difference between the question and these easier problems is that here I am asking that $k+1$ is not a cube modulo the prime $3k+1$, so the same approach does not seem to apply.

Finally, if it turns out that the density is not zero, how does one go about finding the density of those $p=3k+1$ that satisfy that none of the equations $x^3=2$, $x^3=3$, $x^3=k+1$ have solutions?

(Ideally, the techniques lift to other situations, such as studying fifth powers modulo primes $p=5k+1$, etc, but even methods exclusive to the case of cubes are very welcome.)

forces$p \equiv 1 \bmod 3$, since when $p \equiv 2 \bmod 3$ every number mod $p$ is a cube, as 3 is relatively prime to $p-1$. Thus your constraint that $p \equiv 1 \bmod 3$ is automatic given your other constraint that $2 \equiv 3x^3 \bmod p$ has no solution. – KConrad Sep 14 '13 at 12:49