One way, which has some problems is perl2exe.
I used it to connect an ohio lady, a Raleigh NC office, and an Access database. Neither machine had perl installed.
perl2exe offers multi-build modes. There is still a required dll but one option allows you to build .exe with the dll pre-installed (only one program to download). The dll for perl2exe is PerlCtrl.dll.
perl2exe has proven to work for me on Win98, Win2k, and WinXP. Major downside with perl2exe which i havn't worked around yet is Module compilation. Some modules perl2exe uses won't compile when you export to .exe. Here's a link to their
site.
There is an ActiveState solution for standalone. But i haven't paid the dough to use it yet.
http://activestate.com