Alguns sistemas também têm busybox instalado, caso em que você pode executar:
busybox chmod +x /bin/chmod
Desde que você estava pedindo por hacks, eu pensei em outro:
mv /bin/chmod /bin/chmod.orig
cp -a /bin/chown /bin/chmod
Agora você tem um /bin/chmod que é executável, mas na verdade é chown (ou seja, outro binário). Agora tudo o que temos a fazer é sobrescrevê-lo com o binário original.
dd if=/bin/chmod.orig of=/bin/chmod
Ele mantém o sinalizador + x para que você apenas tenha roubado o + x de outro arquivo para este.
É claro que, se todos esses binários alternativos (incluindo o carregador, perl, python, gcc et cetera) forem chmod -x, fixá-lo a partir de um sistema de resgate pode ser a única opção.