if their httpd.conf has incorrect privs set, you could run a script that changes the "user to run as" to root, then set up a script that would run on next reboot to apt-get upgrade and remove the root privs config line. you'd have to wait for the server to go down or reboot however long in the future, but hey it would work.
Your CGI application does not need to be written in bash for you to be vulnerable. If at any point your non-bash CGI program (and this includes PHP, even with mod_php, since it sets the same environment variables), or one of its descendant processes, executes a bash script, you can be exploited.
This is especially bad on systems where /bin/sh is /bin/bash, since /bin/sh gets invoked implicitly by system(3). So you could have a non-bash CGI program invoking a non-bash program using system(3) and you can be exploited.
You're right; thanks! I saw the HTTP_* variables in phpinfo() and assumed they'd be passed on to children through system(), but they actually aren't. In fact the only environment variables passed through look pretty innocuous.
I didn't say it required it. I simply pointed out (albeit sarcastically) that CGI scripts do get written in bash, and people often often make use of sudo within them. I've seen such a beast in production at multiple companies.
The amusing up/down vote war I am watching on my karma gives me hope that at least 50% of HN got it...