From /usr/portage/sys-kernel/linux-headers/linux-headers-2.6.30-r1.ebuild (the latest stable on most architectures): DEPEND="|| ( app-arch/xz-utils app-arch/lzma-utils )" So either linux-headers doesn't really need xz-utils or the stage3 tarball should contain it.
Why? linux-headers tarball is packed .lzma, so it's only required for extracting, and not runtime, and DEPEND will pull it in when required so it's not needed in stage3