> Note that the 'new' label should only appear for stuff that is new
> in that release.

This is not a problem if it says [new in x.y] explicitly.  This way for each version-added/version-changed/deprecated/deprecated-remove directive we will also have a label.

As for the implementation, I'm pretty sure it can be done by changing/redefining all the function/method/class directives.  The directives should then be able to inspect the nodes they contain and see if there are any of the aforementioned directives and turn them into labels.  Not sure if there's a clever way to do it though (maybe a CSS class can be added to the directives and the labels can be added with CSS :after).