Linux distributions without selinux

If you are concerned about which modules and features are compiled into your kernel, you should maintain your own kernel, compiled by you. Debian has a system named make_kpkg to facilitate this process. You can copy over a stable config from /boot to the new kernel source tree and load that into your custom build so you don't have to configure everything from scratch. Then you have complete freedom to manually scan through every single kernel configuration setting, including SELinux.

while it is in the vanilla kernel i presume every distro ships the system with that part enabled.

You can only disable it or recompile your own kernel without it.

title SE-Linux Test System
        root (hd0,0)
        kernel /boot/vmlinuz-2.4.20-selinux-2003040709 ro root=/dev/hda1 nousb selinux=0
        #initrd /boot/initrd-2.4.20-selinux-2003040709.img

Ubuntu and Suse don't come with it in the default kernel, as they use app armor instead. I believe Gentoo uses GRsecurity, so doesn't come with it by default either