Like Thomas said, it depends on the machine. In some, should the dead battery cause a boot failure, a second start will give a normal start-up. You may have to zap the PRAM to get a start, or start from a system CD and then warm boot from the hard drive. Fortunately, the G4s don't show some of the ill-tempered dead battery problems of older Macs with "Old World ROM."
Batteries are reatively cheap if you order on-line, so it's a good idea to keep one around. I have two in the veggie drawer of our frig, stored for future need. Radio Shack has the correct battery as part number 23-026 but you have to look for the number as most clerks don't realize that they carry a Mac PRAM battery, However, RS has grown expensive--about US$15--so I only use them in an emergency.
I get batteries on-line from:
Other World Computing
Operation Headgap Systems
The latter pays the shipping, even if you buy only one little battery,