A peek at the schematic http://www.aurcade.com/games/manuals/00001083.pdf
Shows that those are the ROMS. You will need to reprogram them (with a burner and eraser) and replace any that fail to program, or order replacement EPROMS.
also, you should never remove the sticker on the EPROM, that blocks ambient light to prevent erasure over time. (Note the pattern that the failures occurred in, and the pattern of the removed stickers)

Real quick, that is a bypass cap, it is used to filter out high frequency junk, almost every high speed IC will have one (CPU, RAM, ROM, PIA, and more) If an IC is populated, it's associated bypass cap should be present.
They should always be very close together. According to BloodyCactus they originally were .1uf (which is a pretty common value). If that IC is not going to reinserted, just desolder and remove the broken part, otherwise the IC can be reinstalled while the cap's replacement is on order, but you should still reinstall it eventually.

So, the battery on VS goes into a MB8416, as through a 100r resistor to CS. (the bit with the transistor operates as open while the normal PSU is at 0)

According to the datasheet, the 8416 will hold data down to 2.0V and operates normally at 5.

As the battery is going to through a silicon blocking diode, it drops about .7 volts.

We want the IC to have at least 2v, so we need 2.7v (at least) 3v seems good, but we can go up to 5.
The classic combination of 3 AA's in series gives 4.5 at full charge, and should give a good live.
A 3V coin cell would also work, but might not last as long.

As for battery life, the IC's Datasheet states that it draws 10uA when in stanandby.
A CR2032 has a typical capacity of 240 mAh (until 2v). Which means it should last about 2.5 years.
The A91(aa) battery datahseet does not give figures for discharge at such a low current, so I'll use the lowest one of 2500 mAh at 25mA so if, which gives us roughly 20 years, but we all know that other factors tend to break that (leakage current and other goodies).
Typically, AA's will only last 2-5 years in similar situations.

http://www.johnsarcade.com/vs_downloads/misc/VS_Schematic_%28MDS-02-CPU%29.pdf
http://matthieu.benoit.free.fr/cross/data_sheets/MB8416-20.pdf
http://data.energizer.com/PDFs/cr2032.pdf
http://data.energizer.com/PDFs/E91.pdf

TL;DR
A 3v coin cell should be sufficient, but the classic 3 AA's in series will give you more life, probably.

You sure that's CGA?
CGA uses RGBIHV (Red Green Blue Inensity Horiz Vert), and you seem to have RGBS (which is normal for jamma).
Some LCDs will sync with the composite sync on Hs or Vs (or both). If that is not the case for yours, you can use a sync seperator[1] to get both for VGA's RGBHV.
If you have real CGA RGBIHV, you need what is effectively a specialized DAC (CGA is actually digital) to get VGA out of that.

[1] similar to a LM1881 used in NTSC and PAL, an LM1881 might even work, but I don't know what standards used for that sync. Datahseet here: http://www.ti.com/lit/ds/symlink/lm1881.pdf