Hmm, that's an interesting idea. I would rule that if someone finds the perfect cohort nd they're not quite level 6 yet, then she could still travel along with you and try to learn from you but just wouldn't be able to gain combat experience or be combat-effective until you reached level 6 and got Leadership (at which point we would explain that as the Leadership effects causing you to be able to effectively tutor her in the ways of combat). I've never had someone meet the cohort prior to taking Leadership (or indeed before being able to access the feat), but I like it and I think its more natural this way, so I say go for it if you like the idea--I'll try to make it work