Surprised that only one person has mentioned York. It was seen as the second city in the medieval period, (It was much more substantial relatively in population then than now) and I think Richard II mused about moving the capital there. Assuming only moderate butterflies (the south coast comes under the sway of France/the HRE during early medieval times etc) then it would be the obvious choice.
If we're talking about medieval times then the only other contender as a permanent capital really is Bristol, but that has nowhere near the ecclesiastical or political prestige of York.