For newly created labels, assign a random style

Not exactly random, and not at tag creation, but you can do something similar to the Tag Icons component and use the replaceTagRenderer() from the plugin-api to modify the html of the tags at view (see discourse-tag-icons/common/header.html at master · isabella232/discourse-tag-icons · GitHub).

A function like this would take the tag name, map the tag name to a number 1-6 (i.e. encode the string into base 6 and take the last digit/apply modulo), and add it to the HTML string. It wont be random since the style would be determined by tag name, but it would keep the style the same for all users

The original default render tag function is here: