rschwieb gave an excellent answer, but I thought I'd expand on some of the details, as well as on Hurkyl's comments beneath that answer.
What are free objects?
rschwieb's answer has already pointed out some of the problems with trying to directly generalize the definition of free modules in terms of linear combinations of basis elements, as well as a rough solution. Thus, I want to define free objects more generally, so that we know what we're talking about.
Let $C$ be a concrete category, and let $U:C\to\newcommand\Set{\mathbf{Set}}\Set$ be the forgetful functor (if you're not too familiar with concrete categories, you can think of this category as having objects that are sets with extra structure and morphisms that are functions between these sets that respect this structure).
In our case, $C$ will be the category of modules over a certain rng, and $U$ will just return the underlying set of the module.
A free object $F$ with basis $B\subseteq UF$, is an object such that for any other object $G$, and any function $\phi_0 : B\to UG$, there exists a unique extension $\phi : F\to G$ which is a morphism in $C$. In other words, to specify a morphism from a free object we can freely pick any elements we like of $G$ to send $B$ to.
The free functor
It turns out that in many cases, if we are given a set $X$, we can construct a free object $FX$ with basis $X$, and this assignment $X\mapsto FX$ is functorial. This functor, $F$, is called the free functor, and it turns out to be left adjoint to the forgetful functor.
Brief aside
When discussing modules over rngs, it is important to recall that even if a rng $R$ has a unit, the modules over $R$ as a rng and as a ring are different, because ring modules are required to satisfy the additional axiom that $1\cdot m=m$, whereas we cannot require this for modules over rngs.
Understanding modules over rngs
Let $R$ be a rng. Let $C$ be the category of rng modules over $R$, and let $D$ be the category of ring modules over $\Bbb{Z}\oplus R$ (addition and multiplication given by $(n,r)+(m,s)=(n+m,r+s)$, $(n,r)\cdot (m,s)= (nm,mr+ns+rs)$). Then $C$ and $D$ are isomorphic as concrete categories.
Proof.
If $M$ is a module over $\Bbb{Z}\oplus R$, it is already a module over $R$, since $R$ is a subring of $\Bbb{Z}\oplus R$. Similarly, if $M$ is a rng module over $R$, it is also naturally a module over $\Bbb{Z}\oplus R$, since we can define
$$ (n,r) \cdot m = nm + rm.$$
Thus we have a bijective correspondence between the objects of $C$ and $D$ that preserves the underlying set, and it is functorial as well, since $R$-linear maps are additive by definition, and thus $\Bbb{Z}$-linear as well, and $\Bbb{Z}\oplus R$-linear maps are already $R$-linear.
Conclusion
Thus, since the categories of rng modules over $R$ and ring modules over $\Bbb{Z}\oplus R$ are isomorphic as concrete categories, they have the same free objects as well. Therefore, as Hurkyl suggests, the free rng modules over $R$ are of the form $(\Bbb{Z}\oplus R)^n$.
Furthermore, one can check that the alternative definition of linear combination suggested by rschwieb will also produce the same free objects, since the definition suggested for linear combinations in a rng module is that one should take $\Bbb{Z}\oplus R$ linear combinations.