¿Puedo tener un shebang condicional?

No directamente, no. Lo mejor es escribir una secuencia de comandos de shell Bourne envolvente y que:

#!/path/to/my/wrapper

y el envoltorio comienza con:

#!/bin/sh
for shell in first second third; do
    if /usr/bin/env "${shell}" "[email protected]"; do exit $?; done
done
# We didn't find any of them.
exit 1

Esto le permite a env(1) usar la lista de búsqueda ${PATH} para ubicar los programas, en el orden dado en el ciclo for.