What's my best option at this point...
You are on a contract to deliver. Why mess around spend the $145 on ActiveState's PerlDevKit (Deployment Tools), which you can download now and try free for 21 days if you are sheepish about buying before you try. It is fully documented and has been around a while. I ran into similar issues as you and their product and support helped me solve the issue. There are lots of nice deployment options and even an installer, and you can bind your own icons to the exe and so on... Your customer might even cover the cost. (I don't work for AS)