Other than the advice moritz has already given, you could run perl from a USB device, meaning that it wouldn't have to be installed on the computer, see PortableZIP edition. Since you are for some reason opposed to creating a stand alone exe I think your alternatives are going to be limited.