This blog entry probably isn't interesting to anyone. I'm writing it because Blogger blogs often turn up in Google results and it might be useful to a random searcher. Point: if you have libselinux on your system and want to get rid of it because it doesn't belong in your profile and is masked and frequently causes lots of obnoxious warnings, you probably shouldn't just emerge -C libselinux. You also probably shouldn't just do a emerge --depclean libselinux or even emerge -C libselinux && revdep-rebuild --library=libselinux.so.1. They might not work.
Not only will they not work, the emerge -C libselinux might not even finish correctly. The problem is that coreutils will build against libselinux even if you USE=-selinux. One of the autoconfiggey scripts does it. There's a bug in Gentoo bugzilla but no official action has been taken yet. If you happen to have updated coreutils since libselinux turned up, after you delete /lib/libselinux.so.1, lots of stuff doesn't work. /bin/ls, for example. And plenty of other programs you take for granted, and that emerge needs to finish unmerging libselinux. This was my experience and that of others. Learn from it.
The first thing you need to do is get a coreutils that doesn't need libselinux. First just make sure you need to do this at all: ldd /bin/mv | grep selinux. If no results you're OK. emerge -C libselinux && revdep-rebuild --library=libselinux.so.1 is all you need. Otherwise a new build of coreutils is in order. The person that filed the Gentoo bug kindly provided a couple patches that do the trick perfectly. It took a bit of messing around to figure out exactly where to put 'em, though.
The way I did it was to create a partial portage overlay. It has just one package in it. Hey, might as well learn this stuff. Create the directory /usr/local/portage/sys-apps/coreutils and copy the ebuild from the main portage tree into it. Also copy over the files directory and its contents from the the main portage tree. Apply the ebuild patch to the ebuild, and download the other patch into the files directory. Then run ebuild $fn manifest, where $fn is the name of the ebuild. This builds the manifest file so portage doesn't suspect your ebuilds of mischief. Now set up PORTDIR_OVERLAY in your /etc/make.conf to include your overlay directory (/usr/local/portage). At this point you should just be able to emerge coreutils and you'll get a version with no libselinux dependency. Now you can safely unmerge libselinux, run revdep-rebuild, and drink some delicous beer. I recommend a porter for this occasion, for obvious reasons. Then you can get rid of the overlay, because you shouldn't need it anymore.
If you don't want to mess with overlays you can always just download the straight source of coreutils, patch it up similarly to how Andreas did, and install that; you can just overwrite it with officially sanctioned coreutils whenever you get around to it, or not. However you do it, check your resulting binaries to be sure they don't need libselinux.so.1 before unmerging it. Also make sure the binaries get installed to /bin and not /usr/local/bin so portage, etc. will find them. You knew that.