The question whether there are infinitely many primes in some coprime residue class mod m
is stronger than asking whether there are infinitely many primes with given inertia index in the field of mth roots of unity, which is a special case of Chebotarev's density. The possibility of elementary proofs of the latter was discussed, as you know, over
here.
It seems that Dirichlet's technique is perfectly natural for this kind of questions. Before he started using Euler's ideas on zeta functions, he played around with Legendre's approach (Legendre had tried to prove the result in his 2nd edition of his Théorie des nombres since he had used special cases in his "proof" of the quadratic reciprocity law), but without success.
Another attempt at giving an "elementary" proof was made by Italo Zignago:
His proof was, however, incorrect.
BTW, question 1 goes back to the correspondence of Euler and Goldbach; they tried (in vain) to find a sequence of numbers divisible only by primes of the form $4n+3$. Eventually, Euler convinced himself that quadratic forms $x^2 + my^2$ won't do.
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
Is there an integer $M$ and system of residues $k_i$ such that for $A_i=k_i+np_i$ we have
$\cup A_{i}=\mathbb{N}$
With only finitely many exceptions, $k_i \gt \frac{p_i^2}{M}$
(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.
Best Answer
There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.
Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.
Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.
Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.