You seem to have tried all you can really do before proceeding to:
1) Put the phone in Recovery mode and go from there:
Disconnect your iPhone and turn it off by holding the “Sleep/Wake” button for about five seconds and then sliding the red slider. If your iPhone is already off, there’s no need to turn it on and then off again. Once it’s off, press and hold the “Home” button and plug your iPhone into a Mac or PC with iTunes installed. Keep holding the “Home” button until you see a dock cable pointing to the iTunes icon. iPhones running older software will display a yellow triangle and text which says “Please Connect to iTunes”. Once you see this image, you can release the Home button.
Open iTunes (if it’s not already open)
and you will be told that “iTunes has
detected an iPhone in recovery mode.”
Click “OK” and you will be taken to
the iPhone pane. Click “Restore” and
you’re done, it’s that easy! Depending
on the extent of your iPhone’s ills,
it may take some time to do a full
restore. Once you’re done, you should
again have a perfectly working iPhone.
2) If recovery mode doesn’t work, it’s time to go to DFU (Direct Firmware Upgrade) mode:
To enter this mode, plug in your iPhone and turn it off. Hold down the “Home” and “Sleep/Wake” buttons for about twelve seconds. You’ll briefly see the silver Apple logo and then your phone will appear to turn back off. Release the “Sleep/Wake” button but continue to hold the “Home” button until you see a message in iTunes stating that it has detected an iPhone in recovery mode. Choose “Restore”
It would be good if you tell iTunes to not auto sync:
Another idea is perhaps start with a fresh Library. Start iTunes by pressing alt and create an empty library in another folder in your hard drive. Try to sync from there. please note that this may wipe your phone if you’re not carefully.
If after all this it continues to fail, you may need to go to a Genius bar, but if it’s a 1st gen iPhone, you may be out of luck.