I think the solution to this problem is clear, you should write a C compiler in pure Perl.

Oh man, I'm funny huh? But wait, I have a real answer too!

You mentioned that one reason to avoid XS is company policies forbidding compilers on some machines. I've been there myself and the result was the Krang build system. Krang relies on XS modules the DBI and XML::SAX::ExpatXS but needs to be deployed on compiler-less targets. We created a system to build binary releases of Krang which require only Perl and MySQL to function.

Maybe you can do something similar. Surely your company doesn't ban compilers on ALL machines!

-sam