I just won this on deity as England. It was my first game ever on deity. I usually play immortal, but I've found this scenario easy with every leader on every level I've played it, so I thought this would be a good foray into deity.
It seems like most people use speed of completion to measure success, but I don't find that as satisfying as playing to see what I can accomplish in the time allotted.
To that end, I played to the finish (rushed the Domesday Book with a GE on turn 69) and had won back all of my cities except for Norwich (in the far east) which would have taken another couple of turns to recapture.
This is a good scenario to practice your military tactics. There's no science, no religion, no culture, it's just a brawl.
Here's my tips/suggestions. I haven't watched MadDjinn's video, so these might not be very original.
On the first turn, ally Gwynedd. You'll get two longbows, and the CS might draw off some of the units attacking Chester. Your next CS ally should be Powys for the other two longbows. The longbows are extremely helpful, don't lose them.
In the beginning, you're badly outnumbered. Within the first 11 turns, I lost York, Ipswich, Dover, Lincoln, Norwich, Chichester, Nottingham, and Thetford, in that order. Just fall back, inflict as much damage as possible while doing so, and try not to lose any units. I eventually also lost Winchester. I never lost Exeter nor Wareham, but the latter was down to 0 defense for a number of turns and didn't fall only because I'd eliminated the Norman melee units.
I allied Northumbria and used those units to find Scotland and Galloway which I also allied. The units they gave me allowed me to capture lots of enemy workers that I used to build a road from York to Scotland and then to Galloway. I had excess workers (no unit maintenance cost, right?) and so I built roads on every tile between Northumbria and York which helped me to whittle away at the Norwegians with my knights.
I harassed York (and pillaged its iron) until I had enough units to retake it. That happened about the same time I was closing on Lincoln from the south, so the forces in York couldn't reinforce the forces in Lincoln which made it much easier for me to retake.
Here's one thing I learned the hard way: if you let your alliance with a CS lapse, their units quit fighting and start walking home. If you re-ally with them, you get the units back immediately, but they lose all promotions. Ouch.