epiiさんありがとうございます！返信遅くなりました。

エラーの種類は、500 Internal Server Errorです。
ログを見ると、Premature end of script headers: test.pl, referer: http://<僕のドメイン>/~<ユーザー名>/
となっています。test.plだけではなく、test.rbやtest_py.cgi(Python)も同様のエラーになります。（PHPだけ正常に動きます。）

userdirの設定はしてあります。しかし、AddHandlerの設定はconf.d以下に別ファイルを作って拡張子の指定をしています。
いろいろ調べてみたらsuexeで動くサーバーで時々出るエラーらしいのですが、そこら辺りの原因が詳しく載っている情報がなかなか得られませんでした。僕のサーバーでもsuexecを使用しています。
suexecを外してみたら、Pythonだけが正常に動きました。perlとrbが今度は500エラーではなくダウンロードされる状態になってしまいました。
バーチャルドメインからの接続ではPerlもrubyもPythonも普通に動きます。
何かしらおかしな設定をしている…という部分があるでしょか？

<Directory /home/*/public_html>
  Options ExecCGI
  SetHandler cgi-script .cgi
</Directory>

SetHandler ではなく、 AddHandler でしたね。
すみません (_ _)

1) suexec 無効 の下で Perl, ruby が動かない件について
  AddHandler cgi-script .cgi
とかしていませんか？
この設定だと .pl, .rb という拡張子のファイルが CGI として動作しません。
  AddHandler cgi-script .cgi .pl .rb
などとするか、拡張子を .cgi に変更すると動くと思います。

2) suexec 環境下で CGI が動かない件について
いつも PHP を使っているので、suEXEC はやったことがなかったのですが(!!)、ググりつつ導入してみましたらできたので報告します。
以下手順。
i) apache2-suexec-custom のインストール
  $ sudo aptitude install apache2-suexec-custom
で普通にインストールします。
ii) suEXEC を有効化するディレクトリの設定 (だと思う)
上のインストールが完了すると、
  /etc/apache2/suexec/www-data
というファイルができているので、このファイルに、
  public_html
を一行追加する。
iii) suEXEC モジュールの有効化
(自分の環境では)suEXEC が有効化されていなかったので有効化する。
  $ sudo a2enmod suexec
簡単に切り替えできて便利。
iv) CGI スクリプトの作成
whoami でどのユーザで動いているかを簡単に確認できるので、シェルスクリプトで。

$ vi ~/public_html/test.cgi
#!/bin/sh
echo "Content-type: text/plain"
echo ""
echo `whoami`

v) パーミッションの設定
所有者以外に書き込み権限があるとエラーになるらしい。
  $ chmod 755 test.cgi
700 とかでももちろん動くみたい。
そこら辺は状況に合わせて設定してください。
vi) 動作確認。
http://localhost:8080/~epii/test.cgi にアクセス。
無事「epii」とだけ表示された。

という感じでできました。
途中いろいろ弄っていたため、いくつか設定が抜けてるかも…。

suexecがOFFの場合は、
・全部正常起動。

Perl とか Ruby が suEXEC 環境下で無くとも動かない問題は直ったんですか？

whoaimからのユーザー名取得も正常です。

動いてるということでは…？

ii) suEXEC を有効化するディレクトリの設定 (だと思う)
上のインストールが完了すると、
  /etc/apache2/suexec/www-data
というファイルができているので、このファイルに、
  public_html
を一行追加する。

↑で、「public_html」を末尾に追加するとダメみたいなので、コメントの後に追加している場合には、一行目に持って行ってみてください。


それと、ログが /var/log/apache2/suexec.log あたりに吐かれているかもしれないので、そちらも参考に。
＃どうしてもダメならスクリプトから chown するとかですかね…。

$ man suexec より抜粋。

If suexec is called by a user with name 'username', it will look into /etc/apache2/suexec/username for configuration. If the file does not exist, suexec will abort. By creating several config files, you can allow several different apache run  users  to  use suexec.
The first line in the file is used as the document root (/var/www in the standard suexec) and the second line in the file is used as the suffix that is appended to users' home directories (public_html in standard suexec).
If any of the lines is commented out (with #), suexec will refuse the corresponding type of request. It is recommended to comment out the userdir suffix if you don't need it.

マニュアルぐらい読んでから投稿しろよ、俺。

もう少しがんばって訳すとこんな感じだと思いますがー

'username' という名前のユーザから suexec が呼び出された場合には、 /etc/apache2/suexec/username という設定ファイルを読み込みます。もしこのファイルが存在しなかった場合には suexec の実行は中止されます。設定ファイルを複数作ることにより、いくつかの異なる apache の実行ユーザが suexec を利用できるようにすることができます。
設定ファイルの一行目はドキュメント・ルート (通常の suexec では /var/www が利用されます) を指定します。二行目はユーザのホームディレクトリのサフィックスとして利用されます (通常の suexec では public_html が利用されます)。
これら二行のうちのいずれかが (# により) コメントアウトされていた場合には、 suexec は対応するリクエストを拒否します。必要がない場合には(二行目の)ユーザディレクトリ・サフィックスはコメントアウトすることが推奨されます。

suexec は User ディレクティブで指定されたユーザ名を見に行く…らしいので、特に変更していない場合には編集するファイルは、
  /etc/apache2/suexec/www-data
です。
一行目はドキュメント・ルートなので、例えば、
  /var/www
などを指定します。
二行目はホームディレクトリ以下のどの場所で suexec するかなので、
  public_html
などとしてください。

あとはファイルの所有者やパーミッションに気をつければできると思うんですけど…。

# どうしてもできないなら perl から chown するとかじゃダメですかね…。

aptitude から php5 パッケージを入れて使っています。モジュールです。

やったことないけど CGI + PHP5 は、$ sudo aptitude install php5-cgi で環境は一通りそろうと思いますよ。

# php5-cli とかもあるけど、PHP を HTML を出力する以外の使い方している人っているのだろうか…？