I don’t really know why calling the interpreter with the full path wouldn’t work for you. I use it all the time. But if you want to use the Python interpreter that is in your environment, you should do:
#!/usr/bin/env python
That way you search your environment for the Python interpreter to use.