I've tried various approaches to finding and leveling companions, the method I found that works the best for me is:
1) Don't worry too much about finding them, I'm playing an Irish scenario and I now have the top line of 11 from the raider group (Agasicles to Siwi) by just checking the Irish cities as I did city quests and sold slaves. They show up eventually.
2) Make a 'companion' group. Get 20 to 40 irish infantry and line up companions in front, infantry next, then archers (if you have them) and go hunting. This way your companions always fight first, let them fight till they're knocked out and it protects your real army.
3) Inka (agility based skills) and Connor (int based) are with the archers and have bows + sword-board, Agasicles (int based) is in a group called support with hornman, clerics etc and usually left at spawn or right behind infantry and has javalins + sword-board. All the others in the front group have 2-hand axes, a shield and 2 javelins.
4) Hunt outlaws and scoti raiders for armor, don't buy any except gloves. All companions are now fairly well armored (30+ head, 50+ body, 30+ legs).
5) Hire a merc captain to hold good medium and all heavy, elite troops you free or convert from slaves. It's cheaper than a lair if you get a castle inside 9-10 months from using him. I have him hold back deep in Mumain territory so he doesn't get killed by raiding lords.
6) Hire all companions outside your target group, send them on right to rule quest then dump them (I have interactions on).
That front group of companions mows through infantry, I get each of them up to 3 or 4 skill in trainer, many have it to begin with, the others I give a few points to int to get them there.
I've done no trading what so ever, it's August and I'm around level 20, all the companions are 13 to 16 so they're starting to level up troops. I have an army of 100 troops of light, as they level to medium or I free heavies I dump them in the merc captain who's holding around 80.
My goal for year 1 was to hold at least one city and have all companions around level 20, that shouldn't be a problem. For year two I'll figure out what area I want to hold when starting a kingdom and begin angling to have those castles and cities given to me. By the time I form a kingdom the companions and I will be in the low to mid 20's with several points in trainer. In my experience that's enough to get a good training program. Having armies of 300+ heaving/elites certainly works but it's not necessary with good tactics and use of things like spies and vassal lords.