После двух лет мучений с отладкой веб-скриптов на python3, работающих как cgi и не выводящих кириллицу обычным принтом, я наконец нашел решение: http://pastebin.com/vQaUKjkE
Перехватываем вывод настоящего принта, encode-им его в utf-8 и потом уже выводим на экран.
Посмотрите пожалуйста код, может там есть ошибки которых я не вижу.
Ну и может кому-то это пригодится :)