Northumbria, and maybe another Northern English kingdom joining Scotland instead of England perhaps? Or is that still too equal?
Or find another way to push the border south, maybe down as far as York? I've thought abou this a couple of times, but never put it together - don't know enough history to be able to make it entirely plausibe I guess. But here's some thoughts anyway.
If Alexander III doesn't take the journey to get back to his wife on a stormy night, and hence doesn't fall off his horse and die, is there a possibility of a Scots-Scandanavian empire becoming the dominant player in northern europe? The scottish royal family had multiple ties to the Norwegian one at that time and these would have been strengthened further in all likelihood. If you can then manufacture a Kalmar union equivalent including Scotland that survives, and expand on the trade routes between Scotland and Northern continental Europe which came along later, add in Norway, Sweden and Denmark, and create Scottish-Scandanavian city states in continental europe off the back of this, there's a need to become a major seafaring power to protect your interests around the entire Norh Sea. There's also a need to protect your ports in Northumbria / Teeside and to put infrastructure there. (As an aside, you could, off the back of this, suggest that more exposure to continental europe intoduces more diseases earlier and as such might prevent the Black Death from wiping out such a high proportion of the Scandanavian population, bringing it more in line with the rest of Europe? Don't really know enough about it but I believe the high rates of mortality there had some serious effects?).
The city states on the continent can then have a major impact on the HRE, to the extent of a continental war which leaves the northern kingdom's monarch as the new Holy Roman Emperor.
The seafaring power bit then comes into play during european colonialism, but it's more liekly to follow northern atlantic routes, which wouldn't clash with Spain / Portugal. If expeditions set out early enough, they may even contact the last survivors of the Greenland colonies - legends about ICeland and Greenland could be an impetus to set out on voyages to find them.
In the meantime, a smaller England is less able to control the Welsh and Irish, loses possessions in France, loses territory to the Welsh, etc. Then there's a rump kindom of Anglia which isn't as dominant in the British Isles and has to concentrate on battles with the Welsh and Irish and the dominance of it's empire building neighbour to the north.
Someone will probably come along and knock holes in this, but what the hey.