1. Используйте уже третий питон.
2. Используйте utf-8 в коде.
3. Если уж приспичило, используйте юникодные строки.
4. Не пользуйтесь виндой. Там-поди до сих пор зоопарк из cp866, сз1251 и utf-8 в консолях, шелл скриптах и везде...
5. Приспичила винда, да и вообще, примите за правило: на входе люьой текст приводите к юникоду, на выходе выводите в целевую кодировку.
Из какой и в какую кодировку - читайте в параметрах потокв ввода/ывода. Если там не указано, попробуйте различить связан ли поток с файлом или с терминалом. В файл можно писать любую кодировку, главное правильно сконвертировать и не смешивать. В терминал писать нужно либо в юникоде (если указана кодировка в параметрах потока, то питон сам преобразует), либо в целевой кодировке, которую можно настроить/угадать, предположить и подобрать с нескольких попыток.
Но лучше всего пользуйтесь третьим питоном. Там с юникодом все гораздо проще и однозначнее, чем во втором.
Средний
