nkfやiconvがdllなしで動かないのは、それらがスタティックリンクできるようにインストールされてないから
だろうね。
だから、nkfやiconvをスタティックでビルドしてインストールし、そのあとrubyをコンパイルすればいいはず。
zlibとかgdbmとかはそれでdllのいらないsoを作ったことがある。

で、1.8.4を使うなら、
ttp://ftp.ruby-lang.org/pub/ruby/binaries/mingw/1.8/
にあるmingw32のrubyなら、zlib,curses,readline以外はスタティックリンクになってるみたいだから、
ここからnkf.soやiconv.soを持ってくるだけで動くと思うよ。