1. Replace the crystal
2. Replace the caps - there's not many of them - and my desoldering/soldering is good enough to remove / replace.
3. I can swap out socketed chips. Was nervous about doing so in case there is a fault on the board that damages them and then I end up with two broken PIIs
4. Replace the relays
5. Replace resistors
6. Replace the GD5428 (think I have one in my box of PC boards) - replacing this will push my soldering skills (I'm not very good with drag soldering)
1. I don't expect it's an issue with the crystal since it's oscillating at the correct frequency, the voltage levels on the GD5428 xtal-in pin only need to be meeting the high/low detection threshold of whatever the GD5428 needs, the datasheet will have that detail. But if you want to test the crystal theory, you'd be better to exchange the crystal from the working board. You won't know the characteristics of the existing crystal (i.e. load capacitance, series or parallel load), and if you get these wrong in whatever you select as the replacement crystal, you'll have new problems such as the oscillator not starting reliably, or at all.
2. The capacitors appear to be just general AC decoupling on the DC supply, I don't see how they'd affect the issue. i.e. I expect you'll find that the board would run without the decoupling capacitors.
3. Exchanging socketed ICs is quick and easy with low risk if you're careful about removing/inserting them in sockets. If you can't reliably remove or fit the DIP devices without bending the pins and putting in them in backwards, then this is probably best avoided.
4. You're getting some degree of video signal, so unless it's missing a sync signal from the VGA connector, then I doubt that's causing the issue. They look like fairly generic double pole relays, you can soon test them in circuit. When the coil is energised, both pairs of normally open contacts should be closed. They might also have normally closed contacts which connects to the 'common' pin when the coil isn't energised. Find a datasheet from a similar relay and you'll soon understand the pinout. Besides, the contacts typically start going intermittent before they fail completely, and I'm picking the video issue is permanent.
5. It's even more unlikely you'll have an open circuit resistor unless something is physically damaged. Either way, you should be able to sanity check them in-circuit using an Ohmmeter.
6. I've no idea what drag soldering is, presumably something involving wearing clothes of the opposite gender. Not into that myself. The correct way is to wick off the old solder from the QFP pads, clean with isopropyl, apply no-clean flux, run a single line of solder paste over the pads, position the QFP device accurately on the pads, then reflow with hot air. Only takes a few minutes and you can even wear your normal clothes. If you have a spare GD5428 on hand, this is the first thing I'd try. You might need to find someone to do the soldering for you.