Можно и не абсолютные если питон прописан в PATH, и есть понимание от какого пользователя будет запускаться и какая директория будет текущей.
В любом случае надо убедиться что у пользователя от которого он будет исполнятся есть необходимые права.
не, для 3.4+ тоже. его знатно допилили, UPX сжатие по умолчанию, сборка в один бинарник в 5-7 мб. В общем на работе, для раздачи рабочих скриптов коллегам, раздаю в ехе, собранном через него.