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 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.