I've completely changed my mind but I leave the old answer to explain the comments.
It seems quite likely that there is a choice of residues which misses only the 40 integers
$1, 2, 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 29, 30, 33, 36, 41, 44,51, $
$ 53, 54, 56, 63, 65, 68, 69, 71, 75, 78, 81, 84, 86, 90, 93, 95, 96, 98, 99.$
It arises from the following semi-greedy procedure:
Only worry about integers starting with $s=100$ ($s=90$ is not enough).
At each step, take the smallest integer $t \ge s$ not yet covered and attempt to cover it with the smallest unused odd prime $p$ such that $t+p$ is also not yet covered and $p \le t.$
If there is no such prime then simply use the smallest unused prime (if it is less than $t$, otherwise, STOP!).
Whatever prime is chosen, take the arithmetic progression $A=r+np$ for $n \ge 1$ where $t \bmod{p} =r$
So $1+3n$ knocks out $100,103,106,109,112,115,118,121\dots$ leaving $101$ next. Since $106$ is already covered we use $3+7n$ covering $101,108,122 \dots$ now $2+5n$ works for $102,107,117 \dots$ Next is $104$ and since $104+p$ is covered for $p=11,13,17$ we use $9+19n$.
The residues chosen start out
$[3, 1], [7, 3], [5, 2], [19, 9], [11, 6], [31, 17], [17, 9], [13, 9], [41, 32], [37, 8], [53, 14],$
$ [43, 39], [67, 64], [61, 12], [23, 20], [79, 61], [89, 55], [103, 43], [47, 12], [29, 14]$
Details: I followed this procedure using the $5132$ odd primes up to $49999.$ The number of unused primes less than $t$ (the first uncovered integer) starts at 24 when $t=100.$ It gets as low as 7 a few times, the last being when $t=1419.$ After $t=4925$ there are always at least $10$ unused primes below $t$ and from then on it seems to grow fairly steadily. After $t=33338$ there are (as far as I went) at least $500$ unused primes and after 4341 steps, $t=49980$ with $789$ unused primes available. I used up the remaining primes under $50{,}000$ (without checking if larger primes would be preferred by step 2)
At step $5132$ the prime $43973$ was used for $t=60465.$ This left things with next target $t=60471$ and all $965$ primes $50000 \lt p \lt 60471$ as yet unused.
Other starting values $s$ and the $t$ at which there is no available prime left are:
$[10, 24], [20, 55], [30, 146], [40, 189], [50, 393], [60, 553], [70, 935], [80, 1969], [90, 4898].$
A pure greedy strategy of starting at say $s=1000$ and always using the smallest unused odd prime seems to fail fairly quickly (perhaps in about $s$ steps.) The semi-greedy procedure stems from the idea that the main obstacle is the smallest uncovered integers.
It may be better to not wait too long to use the smallest unused prime. Alternately, it might be better to look a little further in hopes of having $t$ along with two of
$t+p,t+2p,t+3p$ all newly covered.
Old answer (this is left only to explain the comments)
I'll mildly change the notation without changing the question.
For every prime $p_i>p_0=2$ choose a residue $0 \le r_i\lt p_i$ and take the arithmetic progression $A_i=r_i+np_i$ $n \gt 0$ . Let $M=\mathbb{N} \backslash \bigcup A_i $ be the finite or infinite set of missed integers and $m_j$ be the $j$th member of $M$ (set $m_j=\infty$ if $M$ has less than $j$ elements). Once we have the residues up to $r_i$ we do know $M \cap \lbrace 1,2,\cdots,p_{i+1}-1 \rbrace$ and hence $m_j$ up to some point. So $m_0...m_5$ could be $1,2,4,8,16$ but only if we chose $r_1=0$ the first $5$ times. Otherwise we could have $1,2,4,m_4,m_5$ for $m_5 \le 13.$ If we take $r_1=1$ then can begin $1,2,3,6,9,12$ (the next choice is for $p_5=13$)
The greedy procedure is to take $r_i=0$ and get $m_j=2^j.$ The choices $r_i=1$ gives $m_j=2^j+1.$ Gerry suggests taking $r_1=1$ and then making greedy choices. Up to $p_{30}=127$ this gives the $r$ values $1, 0, 1, 0, 1, 0, 2, 0, 3, 7, 2, 0, 4, 1, 1, 3, 2, 5, 3, 8, 4, 1, 0, 1, 0, 1, 1, 2, 1, 1$ and $m$ values $1, 2, 3, 6, 9, 12, 18, 24, 26, 42, 56, 86, 87, 93, 96, 117, 122, 126$ This does not even look like exponential growth (even if extended to $p_{96}=509$. It seems that $r_1=2$ followed by greedy choices might be a little better but still subexponential.
I made the rash
claim: no matter how the $r_i$ are chosen, $m_j \le 2^j.$
NOTE: if my newer conjecture is true then for my chosen residues, $m_{40}=99$ but $m_{41}=\infty$
I made the even rasher claim below but Noam shut it down decisively.
claim: no matter how the $r_i$ are chosen, every integer interval $[x,2x-1]$ contains an $m$ value.
Best Answer
I can't resist some comments. I find it highly unlikely that what you ask is possible. The question seems a bit odd in that it is so specific when more basic questions are open.
In the following some estimates are rough and corrections are welcome. Let $p_i$ be the $i$th prime and $P_t$ the product of the first $t$ primes. For example $p_{10000}=104729$ and $P_{10000} \approx e^{104392.2}.$ This illustrates the estimate $\ln{P_t} \approx p_t.$
Define $h(t)$ to be the smallest $N$ so that out of every $N$ consecutive integers at least one is relatively prime to $P_t$. Equivalently, it is the largest $N$ such that some $N-1$ consecutive integers each have a prime divisor from among the first $t$ primes. Equivalent to that is that $h(t)$ is the largest $N$ such that there is a choice of $t$ residues $ k_{1t},\cdots ,k_{tt} $ with $\cup_1^t A_{it} \supset [1,N-1].$ where $A_{it}=k_{it}+np_i.$
According to this article $h(t) \gt (2e^{\gamma}+o(1))\frac{p_t\ln{p_t}\ln_3{p_t}}{ln_2^2{p_t}}$ where $\ln_j$ is the $j$-fold iterated logarithm. This lower bound seems reasonably close for $t \lt 50$ (the limit of knowledge at the time, and perhaps now). The best known upper bound is $h(t) \lt \ln^2(P_t).$ Using the estimate above that $\ln{P_t} \approx p_t$ we then get that $h(t) \lt p_t^2.$ I have seen it conjectured in a paper from 1976 that perhaps $h(t)=O(t^{1+\epsilon}).$ Note that $p_t \approx t\ln{t}=o(t^{1+\epsilon})$ I don't know how current that is. An off topic note is that sometimes one can find a longer interval of integers all enjoying a divisor from $p_1,\dots,p_{t-1},p_{t+1}$
With the notation above a weaker form of your question is
(I didn't get the motivation to require $p_i$ relatively prime to $M$. Was it just to forbid at least one prime?)
So the situation is that, as far as I know, no-one can say if $h(n) \gt \frac{p_t^2}{M}$ infinitely often, and there may even be reasons to doubt that. This is the case that you may completely change the residues each time you bring a new prime into play. In your case you want a single list of residues.Note that the choices which provide a good example for $h(n)$ may not be good for extending to $h(n+1)$.
$h(9)=39$ as shown by
$$2, 3, 2, 5, 2, 11, 2, 3, 2, 13, 2, 23, 2, 3, 2, 7, 2, 19, 2, 3, 2, 17, 2, 5, 2, 3, 2, 11, 2, 7, 2, 3, 2, 5, 2$$ $$ 13, 2, 3, 2, *, 2, *, 2, 3, 2, *, 2, *, 2, 3, 2, *, 2, 5, 2, 3, 2, 7, 2, *$$
This illustrates that $1+2n,2+3n,4+5n ,6+11n,10+13n,12+23n,16+7n,18+19n$ and $22+17n$ cover all the integers from $1$ to $67$ except for $40,42,46,48,52,60,66.$
The best we can do to extend this introducing the further primes $29,31,37,41,43$ is $h(10) \ge 42,h(11) \ge 46,h(12) \ge 48,h(13) \ge 52,h(14) \ge 60$ etc.The actual values are $46, 58, 66, 74, 90.$ But each requires a new selection of residues.