Você pode fazer isso no nível X11 / Xlib. Veja esta pergunta para saber como lidar com as teclas de atalho globais corretamente em C: Atalho Global com X11 / Xlib
Agora você só precisa de alguma biblioteca Python Xlib; python-xlib parece uma escolha razoável.