I've tried playing as Jämtland, which starts as a lone Catholic count surrounded by many independent Pagans.
Its de-jure Duchy has only 2 counties, but the other one belongs to Norway, so let's ignore that.
Just to its north and east there is an unformed de-jure duchy made up of 5 counties, all pagan, all independent… borrowed money from Jews, hired the cheapest mercenaries I could find, and Holy Warred 3 of them into submission, enough to create the Duchy.
Problem is, creating the Duchy costs 155 gold, I had only ~100, and a monthly income of ~0.45 (once I dismissed the armies, of course).
Caveats:
- Tribal Catholic, with Gavelkind succession law. Being Tribal means the some Councilor actions are different, i.e. there's no "Raise Taxes"
- I already borrowed money from Jews
- You can't expel Jews if you aren't King
- You can't ask money to the Pope if you have free investiture, and you can't switch investiture if you aren't King
- There are no vassals: these are all single-holding counties
- In order to win wars hoping to get prisoners, or to do raids hoping to get enough gold, you need to have enough troops, and without the mercenaries I didn't have enough (and with mercenaries, you easily end up paying them more than you gain)