I actually tried a few solutions and its kind of strange, and might take a lot of coffee time. I'd note i've had a few failed attempts, and have warned where things get dangerous. Read through the whole answer before you tried it. This particular process is safe, as long as you keep in mind why things are being done.
I basically created a second partition, installed windows there from the original partition, and used that to bootstrap the windows install back to the original partition. I've cheated a bit, and cleaned out, but not formatted the old windows partition, since its safer first, though I've posted an answer where I reformatted the drive as well.
You'll need a windows iso, 7zip and some software for resizing drives (I used minitools free from inside windows). You'll also be using things in system properties a lot - you access this by right clicking and my computer - so get familiar with this.

First extract the contents of the windows iso using 7zip into a folder (if you have it installed - rightclick on the iso, and select "extract to" copy this into your tumbdrive. You'll need to use this more than once so keep it handy. You'll also want to keep the minitools installer here.
Install minitools on the current, working system and use that to create a new partition with free space after the current install. You want this to be at least 2.5 gb, and file system dosen't matter all that much since you will be installing a temporary copy of windows XP inside this (in theory, you could make a big partition, install windows XP here, and just work off that. We're assuming though, you want a single, large, functioning windows XP partitions, with a single pc, no external boot devices, and a windows iso. This will make you reboot once, and go back to your current install of windows.
You can now bootstrap the windows installer from windows itself - go to the folder you extracted the windows iso from, and run setup - be sure to select "new installation" rather than update.
.
This will do some stuff, reboot, and get you into the text mode setup. In text mode setup, once again, select new installation rather than repair.
Install xp into the new partition - this gives us somewhere to work on the old partition from. Unfortunately, since the old c: contains the bootloader and the windows installer files, getting rid of it is going to be slightly tricky.
Boot into the new install of windows, and we can start trying to work on clearing out the old install. Since this is a disposable install of xp we won't be using for long, don't bother with particularly correct settings or activation.
We need to do a few small changes to the second install - its still using the pagefile from our old drive so we need to get rid of that, go to system properties, set no pagefile on c: and automatic pagefile on

This is where things get dangerous. If you mess up, you can be left with an unbootable system. We're in the working install right now - and the bootloader is in the other install. The first is a safer option, and should give you a fresh install of windows without too much risk. I'm currently trying to work out how to safely format a system disk, since if you're reformatting cause you have a virus, a simple clear out of the system may not be enough.
If you want a fresh install, rather than a real reformat, things are reasonably simple - delete the old files, other than reformatting, and run setup again from our working install. From the new install (on mine this is set as f: even on the new system), delete all the visible folders on the old system (Documents and settings, windows and program files are what I see on a fresh install. These need to go) . If you can see ntldr and boot.ini , leave them alone. You do not want to taunt the bootloader. Its the one thing we can't fix easily.
When you get into the text mode installer, select c: as your install location (no reformatting), and install it there, going through the install process and the settings again. We're almost done things the 'safe' way, and are in your new, fresh copy of windows. Now, we just need to get rid of our working copy of windows - we can simply remove it from boot.ini(startup and recovery from system properties), set the pagefile back to c: and delete and merge the partition with minitools.
I'll update the answer, when I actually manage to format c:, rather than getting a fresh copy up.
What are you using in the USB Drive? – Doktoro Reichard – 2013-09-04T19:32:55.007
Are you using a USB 2 or did you accidentally try to boot from an USB 3 port. Depending on your model the latter might not work. – Hennes – 2013-09-04T19:42:44.063
2On some BIOSes, a bootable USB flash drive is not listed as a Removable Device, but is listed under Hard Drives – sawdust – 2013-09-04T19:58:05.460
@Hennes it usb 2.0 (completely sure, just checked) – John Demetriou – 2013-09-04T20:45:41.713
@sawdust in BIOS setup removable disk is there, in boot menu (when I press f12) it is not there – John Demetriou – 2013-09-04T20:47:41.003
You don't happen to be plugging your USB in your USB3.0 port do you? (Just had to ask as I had that issue in my workplace USB connected to USB3.0 port are not detected as part of boot from USB / hard drive) – Darius – 2013-09-05T13:37:26.737
@Darius nop, and since many ask I will edit my post :D – John Demetriou – 2013-09-05T13:46:15.383
@JohnDemetriou This is just a random thought... since you said you 'burn' the ISO into USB.. any chance it is considering the USB as a bootable CD instead of removable disk / hard disk...? So maybe after you press f12, just start trying out all the options... ? (and also test the USB on a different PC/laptop maybe after burning it is no longer bootable / detected) – Darius – 2013-09-05T13:55:07.370
@Darius I will try that but in other occasions when I booted from USB i selected removable device not CD/DVD, but I will try it – John Demetriou – 2013-09-05T13:59:09.897
@JohnDemetriou, not to keep flogging a dead horse, but when you clarified about USB 2.0, you specified that the USB drive is 2.0, while the questions were about the actual USB port on your computer. Are you sure the port itself is not USB 3.0? – eisb – 2013-09-18T13:17:17.403
Does Windows boot and how far does it get? (I understand this is XP) Do you have by any chance another similar computer? – harrymc – 2013-09-18T13:24:05.987
I suppose you don't have floppy drive, right? – Luke – 2013-09-21T14:09:41.003
I'm coming late to the party but... maybe your computer can boot from the network. If you have another computer it can act as a startup-server after which you can format, reinstall etc.. xp on the laptop. There are several tutorials on the net depending if you just want to format or completely reinstall xp. This is one. Not exactly what you asked for but it can work if usb and cdrom don't work.
– Rik – 2013-09-23T19:42:00.360@Rik Can you write a full answer with a bit more details? If I remember correctly (I do not have the laptop in my hands now, but I can get it back) network did show up in the boot menu – John Demetriou – 2013-09-23T21:42:52.423