It turns out that there is a much simpler way to accomplish these tasks. Just set LANG variable to en_US.UTF-8 and this should enable you to use Russian UTF-8 in vi editor and in a number of other programs (e.g. PostgreSQL interactive sessions).
This assumes that something like LC_ALL does not override LANG (in which case set it to en_US.UTF-8 as well), and that you are working inside a UTF-8 capable terminal window, and the encoding in the terminal window is set to be UTF-8.
If the command line input of Russian UTF-8 character is broken, set LANG variable to en_US.UTF-8 and then open a new shell. (In this case just setting the variable does not seem to fix what was broken during shell initialization, so the initialization needs to be repeated; at least, it looks this way when one uses bash under Debian.)
It turns out that grep is UTF-8 capable these days: grep "Привет" filename works fine.
Remark: this still does not interpret the keyboard keys as Russian, unlike the Emacs trick. These days I usually just get the Russian strings I need by typing them somewhere in Firefox using the RussKey addon (and then just selecting them by the mouse and pasting them by the middle key of the mouse, when I am under Gnome environment on a Debian Linux machine).
Remark: in Gnome terminal, one can use Right-mouse-click - Input Methods to switch between Cyrillic translit and default (thanks to miserakl for this remark).