The following covers the Russian alphabet:
\documentclass{article}
\usepackage[russian]{babel}
\DeclareTextCommand{\CYRA}{EU2}{А}
\DeclareTextCommand{\cyra}{EU2}{а}
\DeclareTextCommand{\CYRB}{EU2}{Б}
\DeclareTextCommand{\cyrb}{EU2}{б}
\DeclareTextCommand{\CYRV}{EU2}{В}
\DeclareTextCommand{\cyrv}{EU2}{в}
\DeclareTextCommand{\CYRG}{EU2}{Г}
\DeclareTextCommand{\cyrg}{EU2}{г}
\DeclareTextCommand{\CYRD}{EU2}{Д}
\DeclareTextCommand{\cyrd}{EU2}{д}
\DeclareTextCommand{\CYRE}{EU2}{Е}
\DeclareTextCommand{\cyre}{EU2}{е}
\DeclareTextCommand{\CYRYO}{EU2}{Ё}
\DeclareTextCommand{\cyryo}{EU2}{ё}
\DeclareTextCommand{\CYRZH}{EU2}{Ж}
\DeclareTextCommand{\cyrzh}{EU2}{ж}
\DeclareTextCommand{\CYRZ}{EU2}{З}
\DeclareTextCommand{\cyrz}{EU2}{з}
\DeclareTextCommand{\CYRI}{EU2}{И}
\DeclareTextCommand{\cyri}{EU2}{и}
\DeclareTextCommand{\CYRISHRT}{EU2}{Й}
\DeclareTextCommand{\cyrishrt}{EU2}{й}
\DeclareTextCommand{\CYRK}{EU2}{К}
\DeclareTextCommand{\cyrk}{EU2}{к}
\DeclareTextCommand{\CYRL}{EU2}{Л}
\DeclareTextCommand{\cyrl}{EU2}{л}
\DeclareTextCommand{\CYRM}{EU2}{М}
\DeclareTextCommand{\cyrm}{EU2}{м}
\DeclareTextCommand{\CYRN}{EU2}{Н}
\DeclareTextCommand{\cyrn}{EU2}{н}
\DeclareTextCommand{\CYRO}{EU2}{О}
\DeclareTextCommand{\cyro}{EU2}{о}
\DeclareTextCommand{\CYRP}{EU2}{П}
\DeclareTextCommand{\cyrp}{EU2}{п}
\DeclareTextCommand{\CYRR}{EU2}{Р}
\DeclareTextCommand{\cyrr}{EU2}{р}
\DeclareTextCommand{\CYRS}{EU2}{С}
\DeclareTextCommand{\cyrs}{EU2}{с}
\DeclareTextCommand{\CYRT}{EU2}{Т}
\DeclareTextCommand{\cyrt}{EU2}{т}
\DeclareTextCommand{\CYRU}{EU2}{У}
\DeclareTextCommand{\cyru}{EU2}{у}
\DeclareTextCommand{\CYRF}{EU2}{Ф}
\DeclareTextCommand{\cyrf}{EU2}{ф}
\DeclareTextCommand{\CYRH}{EU2}{Х}
\DeclareTextCommand{\cyrh}{EU2}{х}
\DeclareTextCommand{\CYRC}{EU2}{Ц}
\DeclareTextCommand{\cyrc}{EU2}{ц}
\DeclareTextCommand{\CYRCH}{EU2}{Ч}
\DeclareTextCommand{\cyrch}{EU2}{ч}
\DeclareTextCommand{\CYRSH}{EU2}{Ш}
\DeclareTextCommand{\cyrsh}{EU2}{ш}
\DeclareTextCommand{\CYRSHCH}{EU2}{Щ}
\DeclareTextCommand{\cyrshch}{EU2}{щ}
\DeclareTextCommand{\CYRHRDSN}{EU2}{Ъ}
\DeclareTextCommand{\cyrhrdsn}{EU2}{ъ}
\DeclareTextCommand{\CYRERY}{EU2}{Ы}
\DeclareTextCommand{\cyrery}{EU2}{ы}
\DeclareTextCommand{\CYRSFTSN}{EU2}{Ь}
\DeclareTextCommand{\cyrsftsn}{EU2}{ь}
\DeclareTextCommand{\CYREREV}{EU2}{Э}
\DeclareTextCommand{\cyrerev}{EU2}{э}
\DeclareTextCommand{\CYRYU}{EU2}{Ю}
\DeclareTextCommand{\cyryu}{EU2}{ю}
\DeclareTextCommand{\CYRYA}{EU2}{Я}
\DeclareTextCommand{\cyrya}{EU2}{я}
\usepackage{fontspec}
\setmainfont[Ligatures=TeX]{DejaVu Serif}
\begin{document}
\tableofcontents
\clearpage
\section{тест 1}
\section{тест 2}
\section{тест 3}
\end{document}
A more abstract way for getting (almost) all the known cyrillic characters can be obtained with code by David Carlisle (see http://tex.stackexchange.com/a/110016/4427)
\documentclass{article}
\usepackage{fontspec}
\setmainfont[Ligatures=TeX]{DejaVu Serif}
% This code must go after xunicode is loaded (by fontspec),
% but before babel.
\makeatletter
\let\KeptDeclareUnicodeCharacter\DeclareUnicodeCharacter
\def\DeclareUnicodeCharacter#1#2{\@declare{#1}#2!!}%
\def\@declare#1#2#3!!{%
\ifdefined#2\else
\begingroup
\lccode`E=`E \lccode`U=`U
\lccode`A="#1\relax
\lowercase{\endgroup\DeclareTextCommand{#2}{EU2}{A}}%
\typeout{Redefined \string#2}
\fi}
\input{x2enc.dfu}% this contains all the cyrillic characters
\let\DeclareUnicodeCharacter\KeptDeclareUnicodeCharacter
\let\KeptDeclareUnicodeCharacter\@undefined
\let\@declare\@undefined
\makeatother
\usepackage[russian]{babel}
\begin{document}
\tableofcontents
\clearpage
\section{тест 1}
\section{тест 2}
\section{тест 3}
\end{document}
Another way might be to redefine \captionsrussian and the other relevant commands (taken from gloss-russian.ldf of polyglossia)
\def\captionsrussian{%
\def\prefacename{Предисловие}%
\def\refname{Список литературы}%
\def\abstractname{Аннотация}%
\def\bibname{Литература}%
\def\chaptername{Глава}%
\def\appendixname{Приложение}%
\ifdefined\thechapter
\def\contentsname{Оглавление}%
\else
\def\contentsname{Содержание}%
\fi
\def\listfigurename{Список иллюстраций}%
\def\listtablename{Список таблиц}%
\def\indexname{Предметный указатель}%
\def\authorname{Именной указатель}%
\def\figurename{Рис.}%
\def\tablename{Таблица}%
\def\partname{Часть}%
\def\enclname{вкл.}%
\def\ccname{исх.}%
\def\headtoname{вх.}%
\def\pagename{с.}%
\def\seename{см.}%
\def\alsoname{см.~также}%
\def\proofname{Доказательство}%
}
\def\daterussian{%
\def\today{\number\day%
\space\ifcase\month\or%
января\or
февраля\or
марта\or
апреля\or
мая\or
июня\or
июля\or
августа\or
сентября\or
октября\or
ноября\or
декабря\fi%
\space \number\year\space г.}}
\makeatletter
\def\@Asbuk#1{\ifcase#1\or
А\or Б\or В\or Г\or Д\or Е\or Ж\or
З\or И\or К\or Л\or М\or Н\or О\or
П\or Р\or С\or Т\or У\or Ф\or Х\or
Ц\or Ч\or Ш\or Щ\or Э\or Ю\or Я\else\@ctrerr\fi}
\def\@asbuk#1{\ifcase#1\or
а\or б\or в\or г\or д\or е\or ж\or
з\or и\or к\or л\or м\or н\or о\or
п\or р\or с\or т\or у\or ф\or х\or
ц\or ч\or ш\or щ\or э\or ю\or я\else\@ctrerr\fi}
\makeatother
Added April 2013: the forthcoming version 3.9 of babel should solve the problem by checking whether the typesetting engine understands Unicode natively and setting the fixed words accordingly. This version of babel is already on CTAN, but still hasn't found its way in TeX Live. It will soon.