You could use an XSLT on the original XML. The object of XSLT is to transform XML. In this particular example you want to perform a reasonably neutral transform and insert timestamp elements as you go.

This code does a null transform based on a dataset.

<xsl:template match="@*|node()">
<xsl:copy>
    <xsl:apply-templates select="@*|node()"/>
</xsl:copy>
</xsl:template>
[download]

Assuming that you want to recurse over a number of top level nodes, you would use a construct like:

<xsl:for-each select="MyNodes">
<xsl:sort select="@title"/><!--optional sort-->
<xsl:apply-templates select="."/>
<ts><xsl:value-of select="$timestamp"></ts>
</xsl:for-each>
[download]

Where $timestamp is a parameter that has been passed to the xslt engine by your Perl app.