For xterm and mrxvt I can help, but for Emacs I don't, since I don't use it. Anyway, to be able to write cyrillic in xterm, you can edit /path/to/X11/app-defaults/XTerm and use a cyrillic font. Or run xterm like this:
xterm -fn "-misc-fixed-medium-r-semicondensed--13-120-75-75-c-60-koi8-r"
For mrxvt you can edit ~/.mrxvtrc and change "Mrxvt.font" accordingly.