If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called [covering systems][1] and the linked article looks good. 

As you point out, you can use any set of primes, say primes of the form $10^k+3$ (If there are infinitely many, maybe safer to use $10+1, 10^2+1, 10^3+9, 10^4+7, 10^5+3, 10^6+3, 10^7+19, 10^8+7 \cdots$ smallest primes with each number of digits). So a better question might be: if you use all the primes, how sparse a set of residues can you use? Of course this should require each residue to be positive and less then the appropriate prime. the greedy algorithm uses $p-2 \mod p .$
 Since the sum of the reciprocals of the primes diverges, maybe one can do better, but maybe not.




  [1]: http://en.wikipedia.org/wiki/Covering_system