Charles is completely right that this follows from Frobenius' theorem. Since you don't like Galois theory, here is a proof which does not explicitly mention Galois theory. (But it is hiding just out of sight.)
We may assume that $f$ is irreducible as, if $g$ divides $f$, then the set of primes for which $f$ has a root contains the set for which $g$ does.
Let $K$ be the field $\mathbb{Q}[x]/f(x)$. Let $R$ be the ring of integers of $K$, and let $S=\mathbb{Z}[x]/f(x)$. Note that $S$ is a finite index sublattice of $R$ and, if $p$ is a prime which does not divide $|R/S|$, then $R/p \cong S/p$. Also, for any prime $p$ which does not divide the discriminant of $f$, the polynomial $f$ factors into distinct factors in $\mathbb{F}_p[x]$.
Thus, if $p$ is large enough to not divide either $|R/S|$ or the discriminant of $f$, then $R/p \cong S/p \cong \mathbb{F}_p[x]/f(x) \cong \bigoplus \mathbb{F}_p[x]/(f_i(x))$ where $f_i$ are the irreducible factors of $f$ mod $p$. So, for such a prime $p$, prime ideals of $R$ which contain $(p)$ are in bijection with irreducible factors of $f$ mod $p$, and the norm of such a prime is $p^{\deg f_i}$.
So, if $f$ has a root modulo $p$, then
$$\frac{1}{p} \leq \sum_{\pi \supseteq (p), \ \pi \ \mbox{prime}} \frac{1}{N(\pi)} \leq \frac{\deg f}{p}$$
and, if $f$ does not have a root modulo $p$, then
$$\sum_{\pi \supseteq (p), \ \pi \ \mbox{prime}} \frac{1}{N(\pi)} \leq \frac{(\deg f)/2}{p^2}$$
We want to show that
$$\sum_{p: \exists \pi \ \mbox{a prime of} \ R \ \mbox{with} \ N(\pi)=p} \frac{1}{p}$$
diverges. By the above inequalities, it is equivalent to show that
$$\sum_{\pi \subset R, \ \pi \ \mbox{prime}} \frac{1}{N(\pi)}$$
diverges. (Note that the finitely many primes which divide $|R/S|$ or the discriminant of $f$ cannot change whether or not the sum converges.)
Now, we have unique factorization into prime ideals for $R$, so
$$\sum_{I \subseteq R} \frac{1}{N(I)^s} = \prod_{\pi \subset R, \ \pi \ \mbox{prime}} \left( 1 - \frac{1}{N(\pi)^s} \right)^{-1}.$$
The left hand side is the $\zeta$ function of $K$. By the class number formula (see most books on algebraic number theory), $\zeta_K(s) = C/(s-1) + O(1)$ for some positive constant $C$, as $s \to 1^{+}$. So
$$\log \zeta_K(s) = \log \frac{1}{s-1} + O(1) = \sum \log \left( \frac{1}{1-N(\pi)^{-s}} \right) = \sum \frac{1}{N(\pi)^s} + O(1/N(\pi)^{2s}).$$
We deduce that
$$\sum \frac{1}{N(\pi)^s} = \log \frac{1}{s-1} + O(1)$$
so
$$\sum \frac{1}{N(\pi)}$$
diverges.
