Bem, tudo o que você precisa é de um compizconfig-settings-manager e de um plugin compiz-fusion-plugins-extra
sudo apt-get install compizconfig-settings-manager
sudo apt-get install compiz-plugins-extra
Abra o compiz na guia Gerenciamento do Windows, ative o plug-in Extra WM actions marcando a caixa.
defina a ação de atalho "Alternar Tela Cheia" na página de ações Extra WM. Efetue logout e faça login novamente
P.S. para o shell do gnome, use gconf ou tente dconf para ligar a chave
Testado no Ubuntu 14.04 e 16.04