If you want no additional installation under every circumstance, one way or another you need to ship it with a python interpreter. So, in fact you are making the user install the interpreter in an unofficial fashion.
Most linux distributions come with Python nowadays, and you would get problems originating of version conflict very rarely if executed under the same major version. I'd say, just chmod the file appropriately, set the shebang and ship it.
If still insisting on your way, pyinstaller ought to have a way to bundle only the interpreter and binary dependencies together while having the original script stay in plain text, although I have done it under windows and not %100 percent sure it exists under linux.