from what I can tell DBI puts some magic on a hash (fake hash?), but doesn't implement some of the necessary iteration methods

I don't have that problem with my copy of DBI and I see FIRSTKEY in the most recent DBI on CPAN.

So you might want to put some more effort into figuring out why your copy of DBI is broken (or give us more information so we can help you do that).

Note that fixing this particular problem is likely as easy as:

sub DBI::FIRSTKEY { () }
[download]

which you don't even have to put inside DBI.pm. That's certainly much easier than trying to make XS code tolerant of broken modules.