Ok so here is how I bootstrapped my RTR this game :
I took cantwaraburh because it had no allies and a few enemies and was down to one city. I wore them down by basically pouring men into a meatgrinder and then took the city.
I had trained up two companions as envoys already.
Then I found two very small kingdoms that were at war with one another and no alliances to anyone else.
I sent nonaggression treaty offers to both, and when they refused I broke their dicks off. I smashed the sieging army of one, and then the other immediately sent me an offer for a non aggression treaty. After crushing a few more armies of the first guy, I offered him a peace treaty which he accepted.
Now that I've got peace treaties, and both of these guys have accepted me as a sovereign I start sending them things they will respond to., thereby building credibility.
In the middle of this, the biggest bully on the map attacks one of the only two nations that I have any recognition with, so once more into the breech we go.
I get alerted that the faction that owns the whole center of the map is sieging my little puppet state. I'm actually out in the field recruiting guys so all I have on me is a massive army of peasants, so I ride down and kill his main force with an army of 300 peasants + my followers. Bloody battle, and many peasants gave their lives for a chance at the easy life of a mercenary.
While I was looting the first army, the second army jumped me and I honestly have no idea how I managed to pull that one off. I limped away with almost every unit wounded. I won only because the enemy finally routed after taking fire arrow barrages.
Long story longer, my peasant army fought 5 battles just getting back home and then defeated two more pissant armies that were trying to ravage my peasant villages. By the time I got back to the garrison my recruit army was full of pirate captains, heavy infantry, franks, townspeople and every other sort of character you ever find as a prisoner.
Once I was back 'home', sipping mulled mead in the safety of my medieval hovel, I dispatched messages to the puppet factions informing them that I request a mutual defence pact. Considering I'm the one saving them from a larger opponent...
If the bully faction comes down on me and takes out my one city I am going to find their claimant and tear them to shreds and leave the pieces for the crows.