MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

I think that in general if you want to prove that a set of primes is infinite, often you try and compute the rate of growth, or come up with heuristics estimating what its growth should be under suitable "independence hypotheses". I guess that would be another technique. Having positive density is a super-strong condition on a set of primes. Heuristic arguments based on Sato-Tate, for example, tell you that the set of supersingular primes for a non-CM elliptic curve over Q is probably growing something like $O(x^{1/2}/log(x))$. The truth of that statement establishes both that the set is infinite and has density zero all in one stroke. Elkies didn't prove this though, he just took the more naive approach above.
If you can prove any reasonable lower bound for the set of primes which are at most $x$ then it's trivial to find infinite sets of primes with density 0. For example using completely elementary methods one can check that there's always a prime between $n$ and $2n$ (Bertrand's postulate), and hence the number of primes between 1 and $x$ is at least $log_2(x)$ for $x\geq2$ an integer. So now just build an infinite set $C$ of primes by letting the $n$th element be the smallest prime greater than $2^{2^n}$ (or any function that grows much faster than $2^n$). Does this answer your question or did I misunderstand it?