No, FDISK is not for low-level formatting, it was used for partitioning. You need specific software for low-level formatting. In the old days, some bios'es were capable of doing this. Nowadays, some HD manufacturers supply special software that's able to this this, but usually only for their brand of harddisk.

Your best bet it doing what Mark suggests though. This will most likely also work from a bootable Linux cd. This indeed will require you to boot from the optical drive, unless you create a bootable USB stick.