Before each session, in real life, have them do sit-ups, push-ups and pull-ups. If they actually increase any of those, allow them to gain strength points.
Maybe just make it chance. When they gain skill in weapons or some other associated skill, perhaps you determine a percentage chance of strength increase with it. If they fail this time, next time increase the probability. Keeps them intertwined, since weapon skill would probably directly correlate to strength. Perhaps running, acrobatics, etc would also work towards a strength check. Back then I doubt they lifted much weights anyway, sword practice, farming, run tracking, chopping/gathering firewood all would slowly help with the strength.
If you don't like rolling chance, then give a percentage to other skills. Weapon skill increase = 50% towards a strength point. Juggling = 5%. Tracking = 10%. Then as his other skills go up, when he gets 100% he increases a strength.
Only thing I could come up with on the top of my head.