Well, the easiest way to do this with what you have is to make a Win ME start up disk. To do this, insert a floppy into the A drive and open My Computer in ME. Right click on the floppy "A" drive and select "Format" from the drop down menu. In the next windows make sure the "copy system files" box is checked. When it is done, in the My Computer window browse to c:\windows\command and copy the file fdisk.exe to the floppy "A" drive. With the floppy in the system, reboot the computer and it will start to the floppy with just an A:\ prompt, DOS only. Type in FDISK and hit the Enter key. You will now agree with a couple of messages and then you will be able to list, and delete the existing partitions on the system. When finished you will be prompted to reboot to save the changes/deletions.
Now grab your favorite flavor of Linux CD and make sure the BIOS is set to boot from the CD Drive. Boot to this CD and follow the instructions to set up your new operating system.