Yes, there is an elementary proof which requires nothing more than quadratic reciprocity.
Thanks to @lhf for the pointer to Murty’s classical paper on this. I had heard about it but never seen the proof before, and the result of Schur cited in the paper was enlightening. Murty’s paper is already sufficient to answer the OP because it implies we can pick out primes that are $12 \pmod{13}$, but it’s a bit unsatisfying not to include the other two residues by a simpler construction. This is indeed possible!
Note that the set of residues $\{4,10,12\}$ is equal to the set difference of the subgroups $\langle 4 \rangle$ (of order 6) and $\langle 3\rangle = \{1,3,9\}$ in $(\mathbb Z/13\mathbb Z)^\times$. This affords us the following strategy:
- Choose a polynomial $f$ such that the primes dividing $f(n)$ always lie in the subgroup $\langle 4 \rangle$.
- Further select $f$ so that $f(n)$ does not belong to $\{1,3,9\} \pmod{13}$, so that at least one prime factor belongs to the coset $\{4,10,12\}$.
The theorem of Schur cited by Murty assures us that 1 is possible, but in this case it’s a familiar object: since $(\mathbb Z/13\mathbb Z)^\times$ is cyclic, the unique subgroup of order 6 is just the set of quadratic residues, so reciprocity gives us this easily by choosing $f$ so that $13$ is a quadratic residue mod $f(n)$, such as $f(n) = 4n^2 - 13$. To satisfy 2, we just need to tweak it very slightly: $f(n) := 52n^2-1$ will do.
We now proceed with the Euclidean argument. Let $p_1, \ldots, p_k$ be any finite (possibly empty) list of primes congruent to $\{4,10,12\}$, and take $P = 52(p_1 \cdots p_k)^2 - 1 > 1$. Let $q$ be a prime divisor of $P$. Clearly $q$ is odd, and has $52$ (hence $13$) as a quadratic residue, so by reciprocity $q$ belongs to one of the residue classes $\{1,3,4,9,10,12\}$ mod 13. And $q$ cannot be equal to any of the $p_i$ since $P$ is coprime to all of them.
So $P$ is composed entirely of primes in those 6 classes, but since $P\equiv 12 \pmod{13}$ (and $P$ is positive), at least one prime divisor of $P$ does not belong to any of the 3 residue classes $\{1,3,9\}$ mod 13. This divisor is thus a prime congruent to $\{4, 10, 12\}$ mod 13 which does not appear in the original list of $k$ primes, which completes our argument.
Best Answer
A theorem due to Dirichlet (completely proved only later, for example by Weber here) states that every primitive binary quadratic form represents infinitely many primes. The proof is much simpler than the theorem on primes in arithmetic progressions and uses the fact that $(s-1) \zeta_K(s)$ has a nonzero limit as $s \to 1$.
The result can also be deduced from the known fact that each ideal class contains infinitely many prime ideals.