How can I uninstall a Windows Service even if I'm missing the .exe for it?

You should be able to do it using below command:

sc.exe delete <service name>

If you do not have sc on your system... check your resource disk.