You can find the construction of homology with general coefficients and the universal coefficient theorem in Hatcher's Algebraic Topology, which is available free from his website.
The answer to your third question is yes.
The answer to the second part of your first question is yes, especially in the case that we take $G$ to be a field, most often finite or $\mathbb{Q}$, or $\mathbb{R}$ in differential topology. Homology over a field is simple because $\operatorname{Tor}$ always vanishes, so you get e.g. an exact duality between homology and cohomology. Homology with $\mathbb{Z}_2$ coefficients is also the appropriate theory for many questions about non-orientable manifolds-their top $\Bbb{Z}$-homology is zero, but their top $\Bbb{Z}_2$ homology is $\Bbb{Z}_2$, which leads to the degree theory in Milnor you were mentioning.
Cohomology with more general coefficients than $\mathbb{Z}$ is even more useful than homology. For instance it leads to the result that if a manifold $M$ has any Betti number $b_i(M)<b_i(N)$, where $b_i$ is the rank of the free part of $H_i$, there's no map $M\to N$ of non-zero degree. This has lots of quick corollaries-for instance, there's no surjection of $S^n$ onto any $n$-manifold with nontrivial lower homology! Edit: This is obviously false, and I no longer have any idea whether I meant anything true.
But in the end $H_*(X;G)$ is more of a stepping stone than anything else; it gets you thinking about how much variety there could be in theories satisfying the axioms of homology. It turns out there's almost none-singular homology with coefficients in $G$ is the only example-but if we rid ourselves of the "dimension axiom"
$$H_*(\star)=\left\{\begin{matrix}\mathbb{Z},*=0\\0,*>0\end{matrix}\right.$$
then we get a vast collection of "generalized (co)homology theories," beginning with K-theory, cobordism, and stable homotopy, which really do contain new information. In some cases, so much new information that we can't actually compute them yet!
To answer your first question, one way to define (co)homology with local coefficients is the following.
Let $X$ be a space, let $\Pi(X)$ be the fundamental groupoid of $X$, ie. a category with objects points of $X$ and morphisms $x \rightarrow y$ given by homotopy classes of paths. A local coefficient system $M$ on $X$ is a functor $M: \Pi(X) \rightarrow \mathcal{A}b$ from the fundamental groupoid to the category of abelian groups. In particular, $M$ associates a "group of coefficients" $M(x)$ to every point of $x \in X$.
Associated to $M$ is the singular complex given by
$C _{n}(X, M)= \bigoplus _{\sigma \in Sing_{n}(X)} M(\sigma(1,0,\ldots,0))$,
where $Sing _{n}(X)$ is the set of all maps $\Delta ^{n} \rightarrow X$. The differential can be defined using the fact that the groups $M(x)$ are functorial with respect to paths in $X$. Observe that this is a very similar to the usual definition of singular complex with coefficients in an abelian group $A$, which would be
$C _{n}(X, A) = \bigoplus _{\sigma \in Sing_{n}(X)} A$,
except in the "non-local" case, we count the occurances of any $\sigma: \Delta^{n} \rightarrow X$ in a given chain using the same group $A$ and in the local case, we use $M(\Delta^{n}(1, 0, \ldots, ))$, which might be different for different $\sigma$.
This is the locality (localness?) in the name, which should be contrasted with globality of usual homology with coefficients, where the choice of the group $A$ is global and the same for all points.
The definition I have given above is enlightening but perhaps not suitable for computations. Luckily under rather weak assumptions one can use the definition you allude to. Let me explain. Let $X$ be path-connected, let $x \in X$ and consider $\pi = \pi_{1}(X, x)$ as a category with one object and morphisms the elements of the group.
The obvious inclusion $\pi \hookrightarrow \Pi(X)$ is an equivalence of categories and so the functor categories $[\pi, \mathcal{A}b], [\Pi(X), \mathcal{A}b]$ are equivalent, too. But the left functor category is exactly the category of $Z[\pi]$-modules! In particular, we have a bijection between isomorphism classes of local coefficient systems on $X$ and $Z[\pi]$-modules.
If $X$ is nice enough to admit a universal cover $\tilde{X}$, the above allows us to give another definiton of homology with local coefficients, the one you know. Let $M$ be a local coefficient system and let $M^\prime$ be the associated $\mathbb{Z}[\pi]$-module under the above equivalence (which is unique up to a unique isomorphism). Since $\pi$ acts on $\tilde{X}$, it also acts on $C _{\bullet}(X, \mathbb{Z})$ and so the latter is a chain complex of $\mathbb{Z}[\pi]$-modules. We the can define homology with local coefficients to be homology of the complex
$C_{n}(X, M ^\prime) = C_{n}(\tilde{X}, \mathbb{Z}) \otimes _{\mathbb{Z}[\pi]} M^\prime$
One can show that this two definitions I gave agree, that is, for $X$ like above we have an isomorphism $H_{n}(X, M) \simeq H_{n}(X, M^\prime)$.
Best Answer
If $R$ is a ring and $R[x]$ is a polynomial algebra, then you correctly state that $R$ are the coefficients. If now $R\to S$ is a ring map, $S$ becomes an $R$-module, and you can prove/note that $S[x]$ is equal to $S\otimes_R R[x]$: we have "changed coefficients" by taking a tensor product over $R$.
More generally, you can consider $M\otimes_R R[x] = M[x]$ for $M$ an $R$-module, and work with "polynomials" with coefficients in $M$ (caveat: you cannot multiply these.)
In the case of complexes, say $(C,d)$ is a complex of $R$-modules, we can do the same, either compute $H(C,d)$ (with "coefficients in $R$") or pick an $R$-module $M$ and compute $H(C\otimes_R M,d\otimes 1)$, with "coefficients in $M$".
In case $R=\mathbb Z$, the $R$-modules are just abelian groups $G$, so these are our possible coefficients, and when we choose $C = \mathsf{Sing}_*(X)$, we call $H(C\otimes G)$ the homology groups of $X$ with coefficients in the abelian group $G$.
Also note that most of your favourite results about "homology with coefficients" (like the Universal Coefficient Theorem) work in full generality for the first interpretation of coefficients (i.e. $C\otimes G$ for $C$ a complex of abelian groups and $G$ an abelian group, or more generally a ring of homological dimension $\leqslant 1$).