I must admit, that I did not think to much about it until now, but normally there is only /usr/bin/python in the scripts.
Of course, if everybody has /usr/bin/python3 inside his Python3 programs, everything could work (unless some of your apps need special environment vars like PYTHONPATH, what could make it troublesome again).
But still, the standard installation of Debian (and others, as much I know) does not include Python3 by default, you at least have to add it to your installation. That is something, you must tell your customers, when you ship Python3 programs.
And yes, if you're targeting Debian or Debian-like systems, make a deb. It's really not that hard, especially with newer tools like fpm.
A handful of ditros have gone ahead and named it python anyway. A stated motivation has been to encourage adoption of Python 3, but practically they're just shooting themselves and their users in the foot, and ensuring incompatibility with the shebangs defined for every other OS. (I don't think there's any plan to ever switch the default binary name from python3 to python, so this incompatibility may never be resolved.)
It was specifically in response to the troubles caused by having /usr/bin/python be python3 in Arch that the guideline came about: http://legacy.python.org/dev/peps/pep-0394/
/usr/bin/python should always point to python 2 (or nothing) /usr/bin/python2 should always point to python 2 (or nothing) /usr/bin/python3 should always point to python 3 (or nothing)
scripts using a shebang line should not, however, rely on /usr/bin/python pointing to python2, and should only use it when they are source-compatible with both python2 and python3.