Is $n^2 + n + 1$ prime for all n?
Hint $\ \ f(1)=3\,\Rightarrow\, 3\mid f(1\!+\!3n),\ $ e.g. $\,3\mid f(4)=21$
Remark $\ $ Above we used the Polynomial Congruence Theorem
$\ {\rm mod}\ 3\!:\ \color{}{1\!+\!3n\equiv 1}\,\Rightarrow\, f(\color{}{1\!+\!3n})\equiv f(\color{}1)\equiv 0,\ $ for all $\,f\in\Bbb Z[x]$
Alternatively $\,\ 3n\mid f(1\!+\!3n)-f(1)\ $ by the Factor Theorem $\,x-y\mid f(x)-f(y)$
The idea generalizes to a proof that any nonconstant polynomial $\in\Bbb Z[x]\,$ has a non-prime value.
Just because a polynomial $f$ doesn't factor doesn't mean that the number $f(m)$ you get when evaluating $f$ at a number $m$ doesn't factor. The simplest example is something like $f(x) = x+1$. This polynomial is irreducible, hence doesn't factor, but $f(3) = 4$ is clearly composite.
Here is a link showing that no polynomial with integer coefficients can evaluate to primes for all integers.
You want to disprove a statement of the form $\forall n\colon f(n)\text{ is prime}$, that is you want to prove $\neg\forall n\colon f(n)\text{ is prime}$, which is equivalent to $\exists n\colon \neg(f(n)\text{ is prime})$. Therefore, a counterexample is often the easiest and most straightforward way to disprove a general statement. In fact, any proof that merely shows that a $\forall$ statement is wrong without constructing a counterexample (or essentially doing so, but leaving out the details) is frowned upon by some mathematicians as being non-constructive. That being said, maybe you'd like a proof that there is no polynomial $f$ such that $f(n)$ is prime for all $n\in \mathbb N$ (except constant polynomials):
Let $$f(n)=a_dx^d+a_{d-1}x^{d-1}+\ldots+a_1x+a_0$$ be a polynomial of degree $d\ge 1$ with coefficients $a_i\in\mathbb C$, $0\le i\le d$, and $a_d\ne 0$. First we observe tat in fact $a_i\in \mathbb Q$ for all $i$: By plugging in $x=1, 2, \ldots, d+1$, we obtain $d+1$ rational equations in the unknowns $a_i$. Since the powers of $x$ are linearly independant (or look up Vandermonde matrix), there exists a unique solution, which must be rational. Then there exists $M\in\mathbb N$ sich that $a_iM\in\mathbb Z$ for all $i$. By assumption, $Mf(n)$ is $M$ times a prime for all $n\in\mathbb N$. For each prime $p$, there are at most $d$ values of $n$ such that $f(n)=p$. Since $M$ has only finitely many prime factors, $f(n)\mid M$ for only finitely many $n$. Therefore there exists $n$ such that $p:=f(n)\not\mid M$. By reducing $Mf(X)$ modulo $p$, we see that $Mf(n+kp)\equiv 0\pmod p$ for all $k\in\mathbb Z$. This implies that the prime $f(n+kp)$ is $p$ for all $k$. Especially, there are more than $d$ values of $n$ for which $f(n)=p$, contradiction. $_\square$
Trivia remark: On the other hand, there exists a polynomial in several variables with the property that its values are either negative or prime, and all primes occur!