First of all check source files of CHtml and CActiveForm. You will notice $afterRequiredLabel and $beforeRequiredLabel are public static and you can see their default values. Next in CActiveForm’s labelEx function implementation you can see how activeLabelEx is called. I didn’t checked that myself, but what you want to achieve should be as simple as setting relevant variables before calling functions from CActiveForm.
CHtml::$afterRequiredLabel = '';
CHtml::$beforeRequiredLabel = '<span class="required">your personal super star</span> ';
for this you need to create a new class/file called ActiveRecord (like the default code generated by Gii does with the Controller)… and all your AR models that need that property should extend from that clas (ActiveRecord instead of CActiveRecord)