Well, I ended up having to wait until about 1500, when protestantism (and later the reformation) kicked in. Enforcing religious unity with a bunch of states at 10 IA each time was quite straightforward once I'd bribed them enough to like me. Here's a fun screenshot showing everyone being my vassal (except Austria, who rebelled - they will be annexed by my HRE once it forms anyway

) just after the penultimate reform:
And here's the HRE post-formation (I gobbled up a load of Golden Horde territory as Burgandy to the east before forming it):
I'm not quite sure how the game figures out what provinces we get cores on, though. We still have cores on the provinces we had as Burgandy, but we get a few more on some provinces like Chur and Nice, though on most provinces we will have to wait 50 years. Anyone know why we get those few extra cores?