Create a bootable CD image with the tools you need. If you need "all utilities", you won't be fitting it on anything under three or four megs, and even compressed images won't get you that much.
Busybox is a very good start. It contains a ton of small utilities in one small binary. Throw in a light shell (ash?) or use Bash since you've now got 650M of room. You'll probably want ifconfig, route, iptables, netstat, ssh/scp, wget/lynx, ln, cp, rm, mkdir/rmdir, lsof, nmap, ptrace, top, ps, kill, nslookup, minicom, dig and tcpdump to start.
You'll likely also want the wireless tools and maybe pcmcia_cs as well (and with wireless comes snort and the like!).
Compile a kernel with every network device you're likely to encounter built in, as well as every filesystem (for me that is minix, ext2, ext3, ntfs (write support), vfat, iso9660, and qnx) and at the very least enough of ip routing to get SNAT to work so you can run it as a Q&D firewall if need be.
Since you're creating an uebertool, you may also want enough of samba to get into shares and do netbios lookups. Perl would be a good thing to have if you needed to do some munging.
If you think you'll ever encounter highspeed connections you will also want pppd/pppoe and dhcpcd.