It looks like building binutils at the same time as GCC is quite common:
http://stackoverflow.com/questions/1726042/recipe-for-compiling-binutils-gcc-together
This could avoid some of the overhead we currently have in getting to our GCC build. It's at least worth a bit of investigation.
Linuxfromscratch do it in as a bootstrap though and it might be good to understand why:
http://www.linuxfromscratch.org/lfs/view/development/index.html