I'm pretty sure the XP trigger must also be tied to number of battles fought as well as kills, I have also had units get promoted without having got any kills, usually on about their third battle.