NO LEVEL UP??

[Masamune·1600]

So I take it this is a seperate check for each attack? E.g. first attack, 1/16 Strength might go up, if not then second attack 1/16 and so on, rather than having at least sixteen attacks to guarantee a level-up?

Yes. One could attack 16 times and not see an increase. Also of note is that Strength, Spirit, and the like cannot increase by more than one point per battle.