I'm looking for a truly minimal usable linux install: the only requirement for the install is that it be able to install a .deb file (that has no dependencies) from the local file-system. (I'm assuming that if I can do that, I can then use that to bootstrap to whatever I actually need).
An ideal distor for my needs would consists of a kernel and an initramfs with nothing but dpks and init. In reality, I expect I will have to settle for something between that and DSL.
Edit: I'm not looking for an installer per se, but rather something that could be booted via an ISO or via PXE. It doesn't even need to leave the system in a re-bootable state.
As Linker3000 pointed out, what I'm looking for may be closer to a embedded distro than anything else.
I'm currently evaluating Alpine Linux to make a corporate router that boots off a USB stick in about 20 secs. The running payload uses 14MB of the system's 1GB RAM. It's not Debian-oriented but might be worth a look.
"A security-oriented, lightweight Linux distribution based on uClibc and Busybox."
I'd go with busybox + dpkg tools. In fact, busybox build scripts produce a disk image that you could use as a initramfs. I've used that (sans dpkg) + openvpn + ssh to create diskless routers on 16MB of flash.
Note that even if busybox is typically used on embedded systems, you can use any Linux kernel, even the latest and greatest. Hint: if you handle the hardware, compiling the drivers you need (and only those) statically in the kernel and not as modules, makes the package noticeably smaller.
Have look at this list of more than 30 'minimal' Linux distos (with descriptions). One of them will probably meet your needs.
You could install Debian base system. The Debian installer will ask you in the end what roles/features you want. In the end, if you select base system, you get just that. In my experience, a base install with a network connection and access to apt allows you to fill in the rough edges if there are things you need.
Edit: I have done this myself, but it is clearly not uncommon. Check out this related SF thread.