python: Can I run a python script without actually installing python?

Edit: Development of Portable Python has stopped. I will remove this answer shortly.

Check out Portable Python. That should do what you need.

Current versions (as of April 2015) are 2.7.6 and 3.2.5

I decided to go with cx_Freeze.

It created a distro that I was able to simply copy and move to the target machine. Also, it was much easier to use than py2exe; further it seems that it is still being maintained (as of Mar 10, 2011), while py2exe development does not look as active.