I hate to say it, but your laptop seems a little underpowered. For Red Hat 9 and the Fedora Core distributions, the minimum system requirements are 200 MHz CPU, 128 MB RAM. I managed to get Red Hat 9 installed on a 166 MHz CPU once, and another time I got it to run with only 96 MB RAM. Regardless, a minimum specification computer is going to be excruciatingly slow. You could certainly choose an even earlier distribution, but you will give up all the nice bells and whistles that have been invented since then.
There's a distribution called Damn Small Linux which might fit, but I don't know what applications are packaged with it.
You really can't enter your BIOS setup and make the CD-ROM bootable? I guess it might be possible to load the contents of the Linux installation CDs onto a PCMCIA hard drive and install from that, but it would very likely be a time consuming job because it could easily take several tries to get it right. If you do find a solution, please be sure to post the answer here.