すがのです。
みなさんお知恵をありがとうございます。

頂いたお話をまとめると、

1. 環境変数で cert ファイルの位置は上書きできる
2. cert ファイルはスクリプト内でも指定できる

ということですよね。

さっそくどちらも試したのですが状況が変わりませんでした。
ということは cert ファイルの問題ではない、ということになりますよねえ。
ファイルがなかったのでてっきりそれだと思ってたんですが、お恥ずかしい。

試しに OpenSSL をホームディレクトリにインストールして、ruby のビルド時
にそちらを参照するようにしてみたのですが、これだとちゃんと動作しました。

さくらのレンタルサーバ上の openssl の場所を確認してみて、

$ openssl version -d
OPENSSLDIR: "/usr/local/ssl/etc/ssl"

だったので、

RUBY_CONFIGURE_OPTS='--with-openssl-dir=/usr/local/ssl' rbenv install 2.4.1

としてインストールしたら無事動作しました。

cert ファイルの位置も、

$ ruby -ropenssl -e 'p OpenSSL::X509::DEFAULT_CERT_FILE'
"/usr/local/ssl/etc/ssl/cert.pem"
$ ls -l /usr/local/ssl/etc/ssl/cert.pem 
lrwxr-xr-x  1 root  wheel  38 May 11  2016 /usr/local/ssl/etc/ssl/cert.pem -> /usr/local/share/certs/ca-root-nss.crt

という状態で、正常になってるようです。

configure スクリプトが見つけた OpenSSL の場所がなんらかの理由で別のと
ころになってしまうことがある、ということでしょうかねえ。ちょっと気持ち
悪いですが無事動作してくれて良かったです。

みなさんありがとうございました!

--
Sugano Yoshihisa(E)