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.
Note that $a+b\,x+c\,x^2\in V$ if and only if $c=-a-b$. It follows that $a+b\,x+c\,x^2\in V$ if and only if
$$
a+b\,x+c\,x^2=a+b\,x+(-a-b)\,x^2=a(1-x^2)+b(x-x^2)
$$
This proves that $\{1-x^2,x-x^2\}$ spans $V$.
To prove that $\{1-x^2,x-x^2\}$ is linearly independent suppose that
$$
a(1-x^2)+b(x-x^2)=0\tag{1}
$$
Plugging $x=0$ into (1) implies $a=0$. Plugging $x=-1$ into (1) implies $b=0$. Hence $\{1-x^2,x-x^2\}$ is linearly independent.
Best Answer
One way to handle the issue of "how to write these polynomials and define their operations rigorously" would be as so: let
$$\begin{align*}&\text{Poly}(F) \\ &:= \left\{ p(x) := \sum_{n=0}^\infty a_n x^n \, \middle| \, a_n \in F, \exists N_p \in \mathbb{N} \text{ s.t. } a_{N_p} \ne 0 \;\&\; n > N_p \Rightarrow a_n = 0 \right\} \cup \{\mathcal{Z}\} \end{align*}$$
and we say $N_p = \deg(p)$, i.e. $N_p$ is the degree of $p$ (for $p \ne \mathcal{Z}$). Above, $\mathcal{Z}$ is understood to be the zero polynomial, i.e. $\mathcal{Z}(x) \equiv 0$ for all $x$. It is often taken that $\deg(\mathcal{Z}) = -\infty$ to mesh well with later observations. You can take
$$\mathcal{Z}(x) := \sum_{n=0}^\infty 0x^n$$
to make it work better in terms of operations.
Notice in particular how this retains our intuitive ideas of polynomials: sure, we have an upper bound of $\infty$, so it's more like power series, but for a particular $p \ne \mathcal{Z}$ and corresponding $N_p$ (always finite!) we have the equivalence
$$p(x) := \sum_{n=0}^\infty a_n x^n = \sum_{n=0}^{N_p} a_n x^n$$
Then you can define our operations quite simply. Take $p,q \in \text{Poly}(F)$ and $\alpha \in F$ with
$$\begin{align*} p(x) &:= \sum_{n=0}^\infty p_n x^n \\ q(x) &:= \sum_{n=0}^\infty q_n x^n \\ N_p &= \deg(p) \\ N_q &= \deg(q) \end{align*}$$
Then we define
$$\begin{align*} (p+q)(x) &:= \sum_{n=0}^\infty (p_n + q_n)x^n \\ (p\cdot q)(x) &:= \sum_{n=0}^\infty \left( \sum_{i+j=n} p_i q_j \right) x^n \\ (\alpha p)(x) &:= \sum_{n=0}^\infty \alpha p_n x^n \end{align*}$$
We can ensure that $$\begin{align*} \deg(p+q) &= \max \{N_p,N_q\} \\ \deg(p \cdot q) &= N_p + N_q \\ \deg(\alpha p) &= \begin{cases} \deg(p) & \alpha \ne 0 \\ -\infty & \alpha = 0 \text{ (and hence } \alpha p = \mathcal{Z}) \end{cases} \end{align*}$$
where we assume $-\infty + k = -\infty$ for any finite $k$ (and, of course, $-\infty < k$ for any finite $k$).
Using this alongside the field axioms can be used to show, indeed, $p+q,p\cdot q,\alpha p \in \text{Poly}(F)$.