Don't mind what HDToolbox says how big (or small) the hdd is, just create a little partition (smaller than 2GB). If this does not work, reduce the number of cylinders in the install dialogue until the hdd is smaller than 2GB.
Then install 3.1 and your cd driver on it and create an OS3.9 emergency disk. Now you have a bootable floppy with cd-rom driver on it and can use the new HDToolbox to install the whole hdd.
Remember that the boot partition still needs to be below the 4GB limit.
Bye
Thomas