David, Out of the three approaches that you have tried only your third approach would work with ui:inputText, Also the $A.util methods such as toggleClass or removeClass will not be of much help here as they deal with the class of the element in this case its the class of the input box itself.
Short Answer for this behavior is LOCKER SERVICE & SALESFORCE AUTHORED COMPONENTS.
App / Component :
<aura:application access="global" extends="force:slds">
<aura:attribute name="myString" type="String" />
<aura:attribute name="isTest" type="Boolean" default="false"/>
<ui:inputText aura:id="myinput" label="What are you thinking about ? " labelClass="{!v.isTest == true ?'blue':'red'}" value="{!v.myString}" blur="{!c.changeColor}"/>
</aura:application>
Style.css
.THIS .red {
color : red;
}
.THIS .blue {
color : blue;
}
This would set your label to be blue or red based on isTest Boolean value. But changing the isTest attribute inside your javascript controller and helper will not change the class. Because the class assigned to the labeClass attribute is a CONSTANT.
The ui:namespace components such as ui:inputText are salesforce authored components, it will have read access but you cannot dynamically change the attribute unless specified otherwise. For example value attribute in the ui:inputText will be a part of aura: digestCycle and any value change will get reflected, but the attribute labelClass is not listened for.
Controller.js :
changeColor : function(component,event,helper){
component.set("v.isTest",true);
console.log(component.find("myinput").get("v.labelClass"));
component.find("myinput").set("v.labelClass","red");
component.find("myinput").set("v.value","Hello World");
}
Take the above controller for example, it handles the onblur event from the ui:inputText.
component.set("v.isTest",true); will not set the class from red to blue when you set it to true. Because the aura framework does not have the dynamic binding between the v.labelClass and the v.isTest, as the labelClass is a constant.
console.log(component.find("myinput").get("v.labelClass")); you will be able to read the value, just not modify it.
component.find("myinput").set("v.labelClass","red"); again this will not work as the labelClass is a constant. Infact this will throw you a warning.
And finally, component.find("myinput").set("v.value","Hello World"); this will work as value attribute is a part of those attributes which can be dynamically modified.
Output when click out of the inputBox

Alternative Solution :
Probably using this HTML markup as a dynamic lightning component and pass attributes such as class, labelClass etc. Short Version : Build your own input Component with your custom namespace. It will over-come these restrictions enforced by LOCKER and allow granular control over label Class. Atleast this way its reusable. Or you could go with the re-render method as you suggested.
labelClass="{!mycondition ? 'Mandatory' : ''}"
– Renato Oliveira May 20 '17 at 13:19