Can you tell us what part of the laptop is hottest when it does this? Is it perhaps the battery itself that is getting hot? You might want to remove the battery and try the machine without it for a while, and it's possible you'll find that the battery is your only problem. There is a recall on many 15" PowerBook batteries, and one of the symptoms is that the battery gets very hot (and in fact potentially catches on fire and melts). I've pasted the link to the Apple recall page below. If the serial number qualifies, they'll send you a brand new battery in the mail in about a week. (And just an FYI for others, many white iBook 12" batteries, and many PowerBook 12" batteries also qualify for recall...I find that about 1/10 batteries I come across are eligible.)
https://support.apple.com/iBook_PowerBook/batteryexchange/main?id=qp
Also, you didn't mention how much RAM you have, but a G4 with Leopard and only 512MB has to work overtime and can get hot, so if the fan & battery suggestions don't work, you may want to upgrade your RAM if you only have 512MB.