バージョン情報を載せるのを失念しておりました。
バージョン情報は以下のとおりです。
apache2は「apt-get install apache2」でインストールしています。

Ubunts 9.04
Apache/2.2.11


設定は以下のサイトを参考にしました。
http://httpd.apache.org/docs/2.2/howto/cgi.html

suexecは使用していないと思います。
「apache2 -V」の結果で表示されたSUEXEC_BINのパスにはsuexecのファイルは存在していませんでした。

#マニュアル上は「apachectl」となっていますが、
#バージョンが変わってバイナリ名が変更になったんでしょうか？

リクエストアドレスは以下です。
別のhttpサーバがポート80で起動しているので、
リッスンポートを8080に変更しています。

http://[ホスト名]:8080/test.cgi

こんな感じで、cgiファイルに実行権を与えてやると動いたですよ。

DocumentRoot /var/www/
<directory />
Options FollowSymLinks
AllowOverride None
< /directory>
<directory /var/www/>
Options Includes ExecCGI FollowSymLinks
AllowOverride All
Order allow,deny
allow from all
</directory>

ScriptAlias /cgi-bin/ /usr/lib/cgi-bin/
<directory "/usr/lib/cgi-bin">
AllowOverride None
Options +ExecCGI -MultiViews +SymLinksIfOwnerMatch
Order allow,deny
Allow from all
</directory>

ErrorLog /var/log/apache2/error.log

DocumentRoot直下にcgiファイルを置かないといけないのですか？

ScriptAlias を指定してないから、ということではないですよね・・・。
どうも、Ubuntu の apache2 は、CGI を実行させたいディレクトリに、明示的に ScriptAlias ディレクティブを指定してやらないとなんだかうまく動かないみたい・・・。
大嘘書いてたらごめんなさいなのですが。

例えば、/var/www/ 直下に CGI を設置して、 http://www.example.com/test.cgi で実行させるには、

ScriptAlias / /var/www/
    <Directory /var/www/>
        Options +ExecCGI FollowSymLinks MultiViews
        AllowOverride None
        Order allow,deny
        allow from all
    </Directory>

のような感じに書いてやらないと、上手く動かないようですね。
ん〜、でも、500 Internal Server Error なんですよね。
私のところでは、403 Forbidden なんですが・・・。

あと、CGI の実行はデフォルトのようですので、mime.conf を特別いじらなくても良いようです。
私の環境では、mime.conf の AddHandler cgi-script .cgi のコメントアウトはしていません。

それと、ちょっと気になるのが、/etc/apache2/sites-enabled/000-default を直接編集しているようですが、これが原因と言うことはないですよね・・・。
/etc/apache2/sites-enabled/000-default は、/etc/apache2/sites-enabled/default のシンボリックリンクですので、これを直接に編集するのは望ましくありません。
/etc/apache2/sites-enabled/default の方を編集して、
$ sudo a2ensite default コマンドを実行して、
$ sudo service apache2 restart して反映させます。

なお、/etc/apache2/sites-enabled/default はオリジナルファイルなので、出来れば、
$ sudo cp /etc/apache2/sites-enabled/default /etc/apache2/sites-enabled/hoge
などとしてコピーを作り、
$ sudo a2dissite default
$ sudo a2ensite hoge
$ sudo service apache2 restart
として、コピーしたファイルの方を有効にさせたほうが良いかも知れません。

シンボリックリンクを編集したときは、素直にシンボリックリンクが指す実体のファイルを編集することになるだけです
ですから、シンボリックリンクだろうが、その実体だろうがどちらを編集しても、全く同じであり区別する必要はありません

ry さん、教えていただいてありがとうございました。

あと、訂正一つ。
#8 の

私の環境では、mime.conf の AddHandler cgi-script .cgi のコメントアウトはしていません。

は、

私の環境では、mime.conf の AddHandler cgi-script .cgi のコメントアウトははずしていません。

の間違いでした。

そうですか、状況変わらずですか・・・。
そうか、でも考えてみると、500 Internal Server Error ですから、
CGI を実行しようとしたけどエラーになったと言うことですよね、いまさらですが。
CGI が動かない原因の一番多くは、Perl パスが間違っているというのだと思いますが、これは合ってますものね。
あと、もうひとつ多いのが改行コードが間違っているケースですが・・・。
念のためエディタで改行コードが間違ってないか確認してみると良いかも。
あと、こんなページを見つけたのですが、
http://sagittarius.dip.jp/toshi/premature.php
#! /usr/bin/perl --
と言う具合に、-- をつけると直ったとかいう報告もあったりして。
理由はちょっと良く分からないですけど。

zagan による投稿:

.htaccess が用意されてるとか。。。

あぁー、それもありすね。
merrow さん、.htaccess を使用していて、その中身の記述に問題があると、やはり 500 Internal Server Error になりますよ。

petitbootangさん による投稿:

あと、こんなページを見つけたのですが、
http://sagittarius.dip.jp/toshi/premature.php
#! /usr/bin/perl --
と言う具合に、-- をつけると直ったとかいう報告もあったりして。
理由はちょっと良く分からないですけど。

試してみましたが、状況変わらずでした。

パーミッションは755でも777にしても状況が変わらず。
オーナー/グループをAPACHE_RUN_USER/APACHE_RUN_GROUPのwww-data/www-dataに変更してみても状況変わらず。
apache2を再度インストールしなおして実施しましたが状況変わらず。。。。

もう少し色々調べて見ます。

私も petitbootang さんと同じく，ディレクトリのパーミッションを疑います．

Apache はインストールしたことがないので詳しくありませんが，ソースを眺める限り，

merrow さん による投稿:

[error] (13)Permission denied: exec of '/var/www/test.cgi' failed

のエラー文字列を吐く部分は，execve 系のシステムコールが失敗したときに実行されるコードに有るので，
Apache が .htaccess 等の仕組みでスクリプトの実行をブロックしているのでは無く，
本当に実行(exec)しようとして Permission denied になっていると思われます．

そこで，

merrow さん による投稿:

「/var/www/test.cgi」として保存しており、実行権も付与しています。
また、直接コマンド実行すれば正しく動作します。
--------------------------------------
# ls -l /var/www/test.cgi
-rwxr-xr-x 1 root root 79 2010-08-27 18:22 /var/www/test.cgi

# /var/www/test.cgi
Content-type: text/html

Hello, World.
--------------------------------------

コマンドの先頭が # になっていますが，このテストは root でログインして実行しているのでしょうか？

一般ユーザや www-data として実行したらどうなるのでしょう？

以下参考までに，あまりに強力な root で日常的に作業していると，パーミッションの感覚が麻痺してしまいます．

/tmp/www/test.cgi に投稿内容をコピペし，ディレクトリとファイルのオーナー/グループを www-data に，
パーミッションは test.cgi の u=x 以外は全て不許可に設定しました．
以下の実行例では敢えて sudo su しています．

# ls -ld /tmp/www
d--------- 2 www-data www-data 60 2010-08-30 13:56 /tmp/www
# ls -l /tmp/www/test.cgi 
---x------ 1 www-data www-data 78 2010-08-30 13:55 /tmp/www/test.cgi

この状態でも root は test.cgi を実行可能です．

# /tmp/www/test.cgi
Content-type: text/html

Hello, World.

ディレクトリに u=x，ファイルに u=rx のパーミッションを与えて，
ようやく所有者 www-data が実行できます．

そもそもwww-dataや一般ユーザへsu、直接ログインができませんでした。
おそらくこれが原因だと思います。

# su - www-data
Cannot execute /bin/sh: Permission denied

まだログインできない理由まで確認できていないので、本来のCGI実行確認まで至っていません。

www-dataのホームディレクトリまでの各階層や/bin/shのパーミッションを確認しましたがすべて755で問題ないのですが。。。

apache の設定は /etc/apache2/sites-enabled/000-default の <Directory /var/www/> セクションにおいて

- Options Indexes FollowSymLinks MultiViews
+ Options Indexes FollowSymLinks MultiViews ExecCGI
+ AddHandler cgi-script .cgi

他を変更する必要はありません
スクリプトのオーナーは root:root、パーミッションは 0755 でかまいません