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.
Let $(r,m)=\lbrace r+mj \mid j \ge 0 \rbrace$ and $p_1<p_2<p_3<\cdots$ be a list of some or all the primes. You want a list $(r_1,p_1),(r_2,p_2),\cdots$ whose union is the natural numbers (optinally with some natural numbers allowed to be missed). One method to do this is to greedily define $r_i$ to be the smallest integer not in $\cup_{j<i}(r_j,p_j)$. Is this (almost) optimal? I don't know but I will wildly guess that it is and from now on only discuss the greedy choice. If we use all the primes and try to get all the natural numbers starting with 2 then (making the greedy choice) $r_j=p_j$. This becomes $r_j=p_j-1$ (or $r_j=p_j-2$) if we also want to get 1 ( or 0 and 1). In any case the greedy algorithm gives $\frac{r_i}{p_i} \approx 1$ (Well in the very first we could as well have $r_i=0$)
If we use all the primes except $2$ and try to get all the natural numbers except powers of $2$ (and 0) then again $r_i=p_i$. If we try to get all the natural numbers then it would appear that $\frac{r_i}{p_i} \approx \frac{1}{2}$.
Based on this I will say that there is little hope that you can exclude the primes 2,3,5 (or even just 2) and keep $p_i-r_i<100$. I suspect that for each prime $q$ there is a constant $C_q$ so that using the greedy choice to cover all the natural numbers using primes $q$ and greater results in $\frac{r_i}{p_i} \approx C_q$. It looks as if perhaps $C_7$ is something like 0.43.