I've built GCC 4.1.1 using MinGW and MSys, and out of the other C::B forum members I know Ceniza at least has also done so.
Basically, you need to install MinGW and then install MSys. I don't remember whether or not I had to install any additional tools from the MSys category, but I don't think I did. I actually did another build of GCC 4.1.1 just a week or so ago in order to build Ogre from source, and it pretty much worked the same way as it did my first time.
The GCC prerequisites page mentions quite a few tools you don't need to build GCC 4.0 or 4.1 series: in particular, GMP and MPFR are only necessary for 4.2 and later. All you should really need are a full install of MinGW (gcc, binutils, make), MSys, and the GCC sources. Since all I ever use GCC for is C and C++, those are the only two source packages I download and extract.
The first time I built GCC 4, I followed MinGW's GCC 3.4.5 build script (http://downloads.sourceforge.net/mingw/gcc-3.4.5-build.sh?modtime=1136885451&big_mirror=1) as closely as possible. See this page (http://gcc.gnu.org/ml/gcc/2006-09/msg00044.html) for the details. Like any other piece of GNU software, it's at heart a matter of ./configure (http://gcc.gnu.org/install/configure.html), make (http://gcc.gnu.org/install/build.html), make install (http://gcc.gnu.org/install/finalinstall.html). I always set DESTDIR to a temporary staging area for the make install step so that I can then swap different versions of GCC around as necessary.
Here was the process I followed for my most recent build of GCC 4.1.1:
(extract gcc-core-4.1.1.tar.gz and gcc-g++-4.1.1.tar.gz)
(create folder named "gcc-4.1.1-stage" next to gcc-4.1.1)
(open MSys)
cd /I/Projects/GCCBuild/gcc-4.1.1-stage
../gcc-4.1.1/configure --with-gcc --with-gnu-ld --with-gnu-as --prefix=/mingw --enable-threads --disable-nls --enable-languages=c,c++ --disable-win32-registry --enable-fully-dynamic-string
make CFLAGS="-O2 -fomit-frame-pointer" CXXFLAGS="-mthreads -fno-omit-frame-pointer -O2" LDFLAGS=-s bootstrap 2>errlog.txt
make DESTDIR=/I/Projects/GCCBuild/gcc-4.1.1-final install
At this point, gcc-4.1.1-final contains the subfolder "mingw", which contains the main GCC installation. I then copy over MinGW's prebuilt binutils, w32api, mingw32-make, and friends, and I'm ready to go.
Hope that helps!