Looks like cx-freeze won't do it. from the document's FAQ:
cx_Freeze works on Windows, Mac and Linux, but on each platform it only makes an executable that runs on that platform. So if you want to freeze your program for Windows, freeze it on Windows; if you want to run it on Macs, freeze it on a Mac.
At a pinch, you can try to make a Windows executable using Wine. Our experience is that you need to copy some files in manually after cx_Freeze has run to make the executable work. We don’t recommend this option.
Really looks like you will need python installed on at least one Windows machine, even if only to run cx_freeze on it.