O arquivo .desktop não precisa de permissões de execução, seu script .py faz.
braiam@bt:~$ ls -l /usr/share/app-install/desktop/deluge.desktop
-rw-r--r--. 1 root root 1276 Aug 6 2012 /usr/share/app-install/desktop/deluge.desktop
braiam@bt:~$ ls -l /usr/bin/deluge
-rwxr-xr-x 1 root root 289 Jan 27 2013 /usr/bin/deluge
Você deve antes de empacotar o bit executável no script python, que o dpkg irá cuidar do resto.
O arquivo .desktop é um arquivo de configuração lido pelo xdg e possui variáveis próprias configuradas para executar o binário necessário:
cat /usr/share/app-install/desktop/deluge.desktop
[...]
GenericName=BitTorrent Client
X-GNOME-FullName=Deluge BitTorrent Client
Comment=Download and share files over BitTorrent
Exec=deluge-gtk %U
Icon=deluge
Terminal=false
Type=Application
Categories=Network;FileTransfer;P2P;GTK
StartupNotify=true
MimeType=application/x-bittorrent;x-scheme-handler/magnet;
Como você verá, ele tem uma variável Exec
que cuida da execução quando o arquivo é acessado.