According to my documentation the original PowerBook G3 came with Mac OS 8.0, but would not work with the retail version of 8.0 (you would need the retail Mac OS 8.1 if you lost your OEM 8.0 disk for that PowerBook).
That having been said, the PowerBook G3 was pretty much a PowerBook 3400c with the 603e processor swapped out with a G3 processor. So theoretically Mac OS 7.6 should be able to handle all the hardware other than the processor.
The problem with the G3 processor is that if a system doesn't know that it uses a special caching technique it'll over look it altogether. In the case of Rhapsody systems from that era, the G3 would perform at the same speeds as a 603e of the same clock rating (because the G3 was based on the 603e architecture). Apple released a patch for Rhapsody so that pre-G3 versions would work correctly with G3 processors.
I believe that additional software is what tells the system how to make use of the G3 cache when running some version of 7. And that same software tells the system where to
look for the cache when using 8 and later on hardware that wasn't designed for the G3.
Given that, running Mac OS 7.6.x with the upgrade software used for the PowerBook 2400c with a G3 upgrade would be the best combo for getting 7 on one. If the installer doesn't work, installing 7.6.1 and the upgrade software on another system (like a 3400c) and then making a disk image of that volume to install everything on the G3 might work.
... that is how I would attack the issue, but I haven't even seen one of those G3s in a couple years now, so this is just a best guess.
Reference material:
