It's possible, I believe to compile for wince (gotta love that so appropriate name) on a desktop and then move the executable to the PDA but I've never tried so I don't know how easy that is. If you are unable to do that (and I'd pursue that and the other suggestions in this thread first), there is a little goody in the DBI distribution that many people don't know about:
DBI::PurePerl. I came up with the idea for that module for exactly your case: it provides many of the features of full DBI without the need to compile. Simply copy your DBI distro lib tree onto the PDA and in your scripts.pm set the environment variable DBI_PUREPERL to 1. With that setting DBI will try to load its compiled executable and if that fails it will load the pure perl version. The pure perl version is slower in some cases and missing some advanced features but has everything you need for standard CRUD operation. It worked for me on wince 3.0 and I've had reports of it working on Zaurus and other PDAs as well.