その場合にはVIMとは別にiconv.dllを用意することになります。
iconv.dllはLGPLで配布されているライブラリで現在は1.9.0.0が最新版です。
文字コードを利用するアプリケーションには同梱されていることもあるので、検索するとみつかることもあるかと思いますが（PHPやMySQLのツール類に同梱されているのを確認しています）
日本のVIMユーザの場合
http://www.kaoriya.net/
からダウンロードするのが一般的なようです。
見つかったiconv.dllをgvim.exeと同じディレクトリに保存してgVIMを起動する（起動していた場合は終了させてから起動）するとメニューに「ファイル」に文字コードを指定して開く、保存するなどが追加されています。
個人的には同梱してリリースしてもらいたいものです。
iconv.dllの入手先例）
http://www.dll-files.com/dllindex/dll-files.shtml?iconv
http://www.kaoriya.net/
ViIMproved‐Vim完全バイブル
