python初心者なので、見当違いの事を言ってましたら、ご指摘ください。
ここ一週間、ずっと悩んでまして、どなたかヒントだけでも頂けると助かります。

現在の環境

# /usr/bin/python -V
Python 3.5.1

# /usr/local/pyenv/shims/pip3 list
pip (8.1.1)
PyMySQL (0.7.2)
setuptools (18.2)

作ったプログラム

test2.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
import pymysql.cursors

/usr/bin/python test2.py

とすると、エラーは起こらないのですが、

Apache経由のブラウザからアクセスすると、Internal Server Errorとなってしまい、
Apacheのエラーログに以下が出力されます。

  File "/var/www/python.hogehoge.com/public_html/test2.py", line 3, in <module>
    import pymysql.cursors
ImportError: No module named 'pymysql'
Premature end of script headers: test2.py
Traceback (most recent call last):, referer: http://python.hogehoge.com/test2.py
  File "/var/www/python.hogehoge.com/public_html/test2.py", line 3, in <module>, referer: http://python.hogehoge.com/test2.py
    import pymysql.cursors, referer: http://python.hogehoge.com/test2.py
ImportError: No module named 'pymysql', referer: http://python.hogehoge.com/test2.py
Premature end of script headers: test2.py, referer: http://python.hogehoge.com/test2.py

※上記は日付等のエラーログのヘッダー部分は消してあります。
 全て、[Thu Apr 07 19:53:54 2016] [error] [client 111.111.11.11]が先頭についています。

サーバー環境はさくらインターネットのVPSで、Apacheはvirtualhostをいくつか切っていて、その一つに置いています。
お手数ですが、よろしくお願い致します。

2016/04/08 02:29 追記

apacheの設定で、

<Directory "/var/www/*******/public_html/">
    Options +ExecCGI
    AddHandler cgi-script .py
</Directory>

として、CGIとして動かしているという事を言いたかったのです。>Apache経由

# which httpd
/usr/sbin/httpd
# ps auxw | grep /usr/sbin/httpd
root     20000  0.0  0.0 100004   912 pts/1    S+   02:23   0:00 grep /usr/sbin/httpd

apacheはrootで動かしてます。