So, I made a quick hack adding recoding into dvi2tty. It is not very universal and it doesn't determine source encoding from dvi. Target encoding is equial to encoding of source file recode.c. Just recode it so you can read russian letters properly on the display, where you are planning to use dvi2tty, and compile.
Tested under Linux and MS-DOS.
Sources are provided in koi8-r
No proper patch is supplied, but .orig files are kept in the archive. Do a proper patch if you have time and send me.