Do polynomials make sense over non-commutative rings? One could think of polynomials rings as sort of a derived ring (a ring of functions $f: \mathbb{N}^m \mapsto R$ such that $f^{-1}(R \setminus \{ 0 \} )$ is finite), but from what I can tell, we are mostly concerned with solutions to polynomials as equations in $R$. My question is how does this notion of polynomials as functions $f : R^m \mapsto R $ make sense for non commutative rings? For example $r X^2$ may not equal $X r X$ or even $ X^2 r$. Do we consider all permutations of coefficients and indeterminats for the terms of a polynomial or do we just not deal with polynomials over non commutative rings?

Notice the first construction you gave can also be described as the semigroup ring $R[\Bbb N ^k]$, and makes a polynomial ring with $k$ commuting indeterminates. Moreover, the coefficients commute with indeterminates, but not always with each other. 
Of course, you can let go of both these properties and generate a ring of "generalized polynomials," which look like finite sums of finite products of coefficients interleaved with indeterminates. 
I'm not sure that these rings have significant usage (definitely nothing compared to polynomials over commutative rings); however, its key advantage is that evaluation maps work properly. 
For example, in the ordinary polynomial ring $\Bbb H[x]$ over quaternions, $xi-ix=0$, since coefficients commute with indeterminates. But this equation doesn't remain true if you try to evaluate it at quaternion values: $j$ would yield $0\neq 2ij$. But in the ring of generalized polynomials, evaluation works just fine.
Naturally, things are messier than normal for solutions to such generalized polynomials. For example, $ix-xi +1=0$ doesn't have any solutions over $\Bbb H$, but $x^2+1=0$ has uncountably many solutions.
