I've got a CPAN module that does some of this: Data::Sorting. It handles a fairly wide range of sorting requests, but doesn't use your trick of eval'ing a dedicated sub.

There was also talk about a Sort::Records module by Guttman and Rossler that used the eval-a-dedicated-sub technique, but was even more full-featured; unfortunately I've never actually found the code for it...