I had need of a bare-metal sh-elf build of GCC, and since I'm using Ubuntu now I wanted to do it the Debian way. Granted, I like Gentoo's crossdev build process much better. The compiler generated by this process will be named sh-elf-gcc instead of sh4-linux-gnu-gcc with my patch referenced below. Without further ado, here are the steps I followed.

1. Install deps and source packages

   tim@zemus ~/gcc-cross $ sudo apt-get build-dep gcc-4.5 binutils
   tim@zemus ~/gcc-cross $ sudo apt-get install dpkg-cross fakeroot
   tim@zemus ~/gcc-cross $ sudo apt-get source binutils gcc-4.5

2. Build binutils, and add the linker scripts to the generated package

   tim@zemus ~/gcc-cross/binutils $ TARGET=sh-elf dpkg-buildpackage -b -uc -us
   tim@zemus ~/gcc-cross/binutils $ mkdir -p debian/binutils-sh-elf/usr/sh-elf/lib ; cd debian/binutils-sh-elf/usr/sh-elf/lib
   tim@zemus ~/gcc-cross/binutils/debian/binutils-sh-elf/usr/sh-elf/lib $ cp -rf ../../../../../builddir-sh-elf/ld/ldscripts . ; chmod -R 0755 ldscripts
   tim@zemus ~/gcc-cross/binutils/debian/binutils-sh-elf/usr/sh-elf/lib $ cd ../../../..
   tim@zemus ~/gcc-cross/binutils/debian $ dpkg-deb --build binutils-sh-elf ; mv binutils-sh-elf.deb ../../binutils-sh-elf*.deb ; cd ../..

3. Install binutils

   tim@zemus ~/gcc-cross/binutils $ cd .. ; sudo dpkg -i binutils-sh-elf_*.deb

4. Build GCC (Stage 1) (with my patch found in Launchpad Bug #841475)

   tim@zemus ~/gcc-cross/gcc $ patch -p0 < ../gcc-4.5-debian-rules.patch
   tim@zemus ~/gcc-cross/gcc $ export GCC_TARGET=sh4 ; export DEB_TARGET_GNU_TYPE=sh-elf ; debian/rules control
   tim@zemus ~/gcc-cross/gcc $ DEB_STAGE=stage1 dpkg-buildpackage -B -uc -us -d

5. Remove dependency on libgcc1-sh4-cross, and repack the .deb

   tim@zemus ~/gcc-cross/gcc $ cd debian/gcc-4.5-sh-elf/DEBIAN ; sed -e 's/libgcc1-sh4-cross[^,]*,\s//g' control > control.new ; mv control.new control
   tim@zemus ~/gcc-cross/gcc/debian/gcc-4.5-sh-elf/DEBIAN $ cd ../.. 
   tim@zemus ~/gcc-cross/gcc/debian $ dpkg-deb --build gcc-4.5-sh-elf ; mv gcc-4.5-sh-elf.deb ../../gcc-4.5-sh-elf*.deb ; cd ../..

6. Install GCC

   tim@zemus ~/gcc-cross $ sudo dpkg -i cpp-4.5-sh-elf*.deb gcc-4.5-sh-elf*.deb

Be warned: Even though stage1 should generate a static libgcc, this compiler will refuse to link against it. However, as long as your code doesn't depend on libgcc in any way, you should be fine.