К своему удивлению, я обнаружил, что это
возможно сделать, по крайней мере, в MS Office 2013.
1) На первой странице помещаем в колонтитул (верхний или нижний) прямоугольник нужного нам цвета на всю страницу.
2) Ставим галочку Different Odd & Even Pages.
3) В колонтитул на второй странице помещаем такой же прямоугольник, но другого цвета.
4) PROFIT!