I'm curious about that too. Free promotions don't affect a unit's experience level, like Tristan_C mentioned.But you need a level 4 unit to be alowed to build the HE.
How do you solve this issue without going to war?
However, one possibility is to modify the game. The XP limit from combat with Barbarians is normally 10 points, but this value can be increased. This certainly changes the game, especially on isolated starts and with Raging Barbarians, because it allows you to build an experienced army without any real warring. But the same limit / advantage will of course apply to the AI.
Go to Beyond the Sword/Assets/XML/GlobalDefines.xml
Code:
<Define>
<DefineName>BARBARIAN_MAX_XP_VALUE</DefineName>
<iDefineIntVal>10</iDefineIntVal>
</Define>