According to a paper "Optimal Irreducible Polynomials for $GF(2^m)$ Arithmetic" by M. Scott,
"it is in practise always possible to chooose as an irreducible polynomial either a trinomial... or a pentanomial." [talk slides] [PDF link]
In random number generators irreducible trinomials of various degrees with three nonzero binary coefficients are associated with the names Tausworthe-Lewis-Payne.
Added: It has been known since Gauss that there are lots of irreducible polynomials over a finite field, basically the analog of the Prime Number Theorem for such polynomials. Among the $2^m$ (monic) polynomials over Z/2Z of degree $m$, approximately $1/m$ of them are irreducible.
We can eliminate the possibility of first degree factors by inspection, for divisibility by $x$ or $x+1$ would imply respectively a zero constant term or an even number of nonzero terms in the polynomial. So the first case to test for irreducibility is the trinomials of degree $m$. With leading and constant coefficients accounting for two of the three nonzero terms, there are but $m-1$ possibilities to test, and by symmetry of $x$ → $1/x$ substitution, we can restrict the middle terms to degree ≤ $m/2$.
If none of those pan out, we have the richer supply of pentanomials to test. Indeed you seem to have hit upon a seam of cases where trinomials will never work out, namely degree $m$ a multiple of 8 [PS] (Swan, 1962).
The work then comes down to testing all the $\binom{m-1}{3}$ binary pentanomials $p(x)$ until we find one that's irreducible. Your application might make other conditions, perhaps similar to those considered in Scott's paper above, attractive. Given the modest degrees you are working with, trial division (taking $p(x) \; mod \; q(x)$ for all $q(x)$ of degree ≤ $m/2$) should be fast enough. [Remember, we shouldn't have to test more than O(m) possibilities before we find success.]
There is a fancier way [PDF] to test polynomials for irreducibility over GF(2). A necessary condition for binary polynomial $p(x)$ to be irreducible over $GF(2)$ is that:
$$x^{2^m} = x \mod p(x)$$
In fact Gauss showed for prime q that $x^{q^m} - x$ is precisely the product
of all monic irreducible polynomials over $GF(q)$ whose degrees divide
$m$. [From this he deduced the count of monic irreducible polynomials of
degree exactly $m$ is asymptotically $q^m/m$ as $m \rightarrow \infty$.]
For $q = 2$ it follows that if $p(x)$ is irreducible of degree $m$,
it divides $x^{2^m} - x$ over $GF(2)$, i.e. the congruence above.
Rubin (1980) proposed a necessary and sufficient test for irreducibility,
combining the above with some additional steps to rule out the possibility
that $p(x)$ might be the product of some irreducible factors whose degrees
properly divide $m$. [While the degrees of the irreducible factors would
naturally sum to $m$, having all the irreducible factors' degrees divide
$m$ would be somewhat special, unless of course there is only one factor.]
The additional "sufficiency" steps are to check for each prime factor
$d_i$ of $m$ that:
$$GCD(x^{2^{m/d}} - x, p(x)) = 1$$
That is, if $p(x)$ were to have an irreducible factor of degree $k$ properly
dividing $m$, it would crop up when taking the gcd of $x^{2^{m/d}} - x$ and
$p(x)$ if $k$ divides $m/d$.
Since then a lot of ingenuity has been applied to efficiently doing these
steps. Of course the necessary condition lends itself to repeated squaring,
computing $x^{2^{k+1}} = (x^{2^k})^2$ mod $p(x)$, for $k$ up to $m-1$. We
can take advantage here of the fact that the multiplication we're doing
is a squaring and advantage of the sparsity of our $p(x)$ as a pentanomial
when doing reduction mod $p(x)$.
As the report by Brent of work with Zimmerman (linked above) points out,
this repeated squaring gives with each (fairly inexpensive step) linear
progress toward the "exponent of the exponent" $m$. There is also a way
to progress farther with greater computational effort by modular
composition.
That is, suppose we've already arrived at:
$$f(x) = x^{2^k} \mod p(x)$$
and
$$g(x) = x^{2^j} \mod p(x)$$
Then:
$$f(g(x)) = x^{2^{k+j}} \mod p(x)$$
Thus composition of two polynomials $f(x)$ and $g(x)$ mod $p(x)$ can
replace a number of repeated squaring steps. But composition mod $p(x)$
is more expensive than squaring or even than multiplication generally
mod $p(x)$. So as Brent points out, practical advantage for using
modular composition lies at the final stage(s) of evaluating the
necessary condition. E.g. at the end one modular composition might
replace $m/2$ repeated squarings.
As far as the "sufficiency" conditions go, Gao and Panario outlined
an improvement over a naive implementation of Rubin's tests in this
1997 paper [PDF], basically sequencing the gcd computations in
an expedient order.
Best Answer
For (2), I suspect it will be very hard to characterise all such polynomials, but one approach would be to consider a result from Polya and Ostrowski (1920) which states that every integer to integer polynomial must be a linear sum of binomial coefficients.
The answer to the other two parts is yes: Consider $(x-1)(x-2)\ldots(x-n)$, which clearly works.
Just as an aside, your definition of "irreducible" is not what most people mean -- for instance, $x^5-x=x(x-1)(x+1)(x^2+1)$ is reducible.
As a double aside:
Let $P(x)=(x-1)(x-2)\ldots(x-n)+pn$ for a prime $p>(2n)!\,$ Then we know that, by iterated triangle inequality, the polynomial $P(x)$ has no complex roots of magnitude less than $n$ (Suppose $|\alpha|<n$ is a root. Then $|(\alpha-1)(\alpha-2)\ldots(\alpha-n)|<(2n)!<pn$). Now suppose $P(x)=Q(x)R(x)$ for integer polynomials $Q,R$. Then the constant term of one of the polynomials is divisible by $p$, so the constant term of the other polynomial has absolute value at most $n$, so by Vieta's formula, it has at least one root with absolute value at most $n$, a contradiction.
Thus the family of $P$ above is an infinite family of solutions to the original question.