高尾です。

スクリプトの外(external)から入力された文字列の文字エンコーディングを
default_internal に変換して、Stringオブジェクトを返す関数
rb_locale_str_new や rb_external_str_new を Readline モジュールで使って
みました。

以下、2 点ほど気づいた点を報告します。

rb_external_str_new_with_enc は、以下の修正をする必要があると思います。
今のままでは len に 0 を渡したときに、strlen が呼ばれませんでした。

Index: string.c
===================================================================
--- string.c    (revision 19861)
+++ string.c    (working copy)
@@ -523,7 +523,7 @@
 {
     VALUE str;
 
-    if (len == 0 && !ptr) len = strlen(ptr);
+    if (len == 0 && ptr) len = strlen(ptr);
     str = rb_tainted_str_new(ptr, len);
     rb_enc_associate(str, eenc);

それと、str_conv_enc 関数は taint を伝搬していないような気がします。
自信がないのですが、以下のような修正が必要ではないでしょうか。

Index: string.c
===================================================================
--- string.c    (revision 19861)
+++ string.c    (working copy)
@@ -510,6 +510,7 @@
        len = dp - (unsigned char*)RSTRING_PTR(newstr);
        rb_str_set_len(newstr, len);
        rb_enc_associate(newstr, to);
+        OBJ_INFECT(newstr, str);
        return newstr;
 
       default: