This solution allows adding a 'New!' flag to list items via the use of a special column in a custom list, as well as one line of XSL code.
The first thing I do is I create a Yes/No column in my list (you can also create this column as a Site Column if you think you're going to be using it in more than one list or library). For the example, we're going to call this column 'NewYN.'

(If you prefer, you can use a Choice column with two menu options, 'Yes' and 'No,' instead.)

Then in my custom Style Sheet, I add the following code:
<xsl:if test="(@NewYN = 'True')">
<font size="1" color="#FF0000" ><xsl:value-of select="' ~ NEW!'"/></font>
</xsl:if>
In my example, I'm using the colour red (FF0000). You can change this colour to any colour of your choice. (For an article about Web Color Reference, click here.)

The last step woudl be to modify the Content Query Web Part as appropriate so it can read your style sheets.