What is a basis for dual space of all polynomials over a field? I think of the vector space of polynomials as isomorphic to the space of all "infinite column vectors" with finite non-zero prefixes. However, the dual space "infinite row vectors" can have infinite non-zero prefixes (consider for example the "row vector" associated with the functional that sends a polynomial to the sum of its coefficients). So I don't see how one would construct a basis: clearly the entire dual space is not linearly independent, but any set of vectors with only finite prefixes would not span (since you would need an infinite sum of them to get e.g. the sum-of-coefficients functional). So what is a basis?
Also: how can I formalize my notion of "infinite column/row vector"? Should I think of them as sequences or something?
 A: The notion of "infinite column vector" can be formalised as "sequences in $k^\mathbb{N}$ with finite support", as in a sequence taking values in the field $k$, with only finitely many elements being nonzero. Even more concretely, such a sequence can be viewed as a function $f: \mathbb{N} \to k$ having finite support. Note that this space has a countable basis $\{e_i\}$ for $i \in \mathbb{N}$, where $e_i$ is the sequence having $1$ in position $i$, and otherwise $0$. So this space has countably infinite dimension. 
As you've noticed, the dual space is $k^\mathbb{N}$, the space of all sequences taking values in $k$. For any functional $\phi$ in this space, you may build such a sequence by looking at $\phi(e_i)$ for each $i$, and knowing these values uniquely determines the functional. In particular, it is relatively easy to specify functionals in this space, however the dimension is uncountably infinite, and so any basis will be uncountably infinite too. 
I think that here you have to appeal to the axiom of choice to even guarantee the existence of a basis, and a constructive approach is hopeless. Intuitively, the reason why a basis is so hard is that it guarantees any element of the space may be written as a linear combination of finitely many basis elements. That along with linear independence means any such basis is going to have to be "super weird" in some sense.
