NetBSD is a bit easier to run on 8MB systems these days. Still not super easy, but less fat to trim off. I think you might still need to trim down the default kernel, but at least there is a premade config for that (GENERIC_TINY)
If you're daring, it should work on 4 MB machines... ;)
yes, my Linux kernel is 3.4M, bz2 compressed. Unfortunately, some things are no more possible to get removed from the kernel, like the xattr in ext4.