Thanks for the details of what you've tried. Every detail you can remember increases the chance that someone can spot the problem.
My read is that you've documented beyond much doubt that a clean install is what you need. Restoring your system was a good try, but I don't think that would change much outside of the /system folder. Even if we think it did, the evidence you provided tells me that some files from the first Xcode installation remain. I would be looking for files created on that date and checking perms in places like the root directory, /tmp, /usr/share/sandbox, etc. I would also advise
renaming /Developer as written in the +Book of the Dead+. I didn't invent that instruction; it was distilled from dozens of case histories in this forum.
You might also try one of the 3rd party tools that's out there for cleaning Macs. I've never tried any of them though, so can't make a recommendation.
Oh... erm... You
did restart your Mac at some point since the problems started, right?
Re installing only gcc, have you been to the Developer Tools page at the connect.apple.com site? Select Downloads on the home page, and in the next page select Developer Tools from the lower right panel. I found 2 downloads that appear to be full gcc installers: Xcode Legacy Tools and GCC 4.2 Developer Preview 1. The other gcc downloads seem to be updates. I might try gcc 3.1 in the legacy tools. It's probably all you need, and if not you'd be good to go for an update.
Of course, you could always download directly from the gnu site, just you might need to be a rocket scientist to install one of those packages. I'm guessing it would be a learning experience. There's also something to be said for using a 3rd party installer, since it probably wouldn't be affected by whatever is stopping the Apple installer(s).
Sure hope some small part of the above turns out to be useful. But in any case, please let us know how you resolve the problem.