Depending on how it is calculated this could be a better exploit than you originally posted. For example, take a hero that costs 100 gildar to recruit.
With cruel it now would cost you 150 gildar, but with natural leader it now costs you half of this new amount, or 75 gildar. It is not clear if they mean 50% more of the base cost and 50% less of the base cost. If it is not the base costs that they consider, then the exploit gives you,
+1 attack with a -25% off the cost of recruiting champions.
But if it is calculated off of the base cost, then you are completely correct at +1 attack for free.
As for the comment:
Is it really an exploit though if you have to spend 2 points at Sovereign creation? ...
you gain a point when taking cruel, and use a point taking natural leader.
Possible modification to Natural leader:
Natural leader could give maybe a -25% off recruitment of champions and maybe a -25% to upkeep costs of units, as people naturally want to fight for this person.