Debian has toochain-source and the related packages. These make building cross toochains really easy if you are not trying to do anything fancy. Apparently soft float is a bit too fancy. Another problem with toolchain-source supposedly is that it gets patches slowly. The debian gcc package recommends using the gcc package directly instead of toolchain-source.
Which one is chicken and which one is egg? Well - starting with gcc is probably most sensible. I did this in several passes.
One problem is that the debian/rules is not prepared for cross compiling. The debhelper stuff expects the sunrpc lib to be installable but it is not cross compilable.
With furious tweaking I managed also to add a softfloat toolchain for ARM into scratchbox.
All the debian ARM distros I could find were hard FP. So I'm slowly recompiling stuff for softfloat. Mostly things go quite fine - apt-get source, debian/rules build, fakeroot debian/rules binary. Occasionally linking fails as the preinstalled dev libs are hard FP. Might be wisest to start with the already installed -dev packages and rebuilt and install them. Another trouble is autotools versions. Seems that e.g. the current gcc-3.3 source in debian expects mixed versions of autotools. Scratchbox also sometimes manages to slip native (instead of arm) stuff into the debs.
I have not yet managed to build perl. Perl is handled specially in scratchbox.
In the end it is probably easiest to just use crosstool. As scratchbox seems to be getting better at supporting foreign toolchains, crosstool built toolchains can also probably be used with scratchbox. With crostool-0.40 I only had to specify a more recent linux kernel version to get a softfloat toolchain built.