You're getting close. This should give you a compile error:
<xsl:param name="n" select="1"/>
<xsl:for-each select="uid">
<xsl:call-template name="replacement">
<xsl:with-param name="n" select="$n"/>
</xsl:call-template>
<xsl:param name="n" select="$n+1"/>
</xsl:for-each>
because you can't use xsl:param here. (If you don't get an error, it's a bug in your XSLT processor). However, what you are trying to do is basically flawed, because XSLT, as a functional programming language, doesn't have updatable variables. You need to think of this as a function: calculate the variable $n as a function of something in your input. It might be as simple as position(), or something more complicated involving xsl:number.
Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference