I really think this information might help, if not, I promise not to post anything else. :)

This is a sample program I run:

'''
# -*- coding: utf-8 -*-
import sys
import locale

de = sys.getdefaultencoding()
pd = locale.getpreferredencoding()
print de, pd

s1 = 'سلام'
print s1
s2 = u'سلام'
print s2
'''

I tried to run it before and after applying suggested patches.
Before applying any patch:

'''
Python 2.7.5 (default, May 15 2013, 22:44:16) [MSC v.1500 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
ascii cp1256
ط³ظ„ط§ظ…
سلام
>>> s3 = 'سلام'
>>> s4 = u'سلام'
>>> s3
'\xd3\xe1\xc7\xe3'
>>> s4
u'\xd3\xe1\xc7\xe3'
>>> print s3
سلام
>>> print s4
ÓáÇã
>>> s = u'Русский текст'
Unsupported characters in input
'''

After applying loewis's patch:

'''
Python 2.7.5 (default, May 15 2013, 22:44:16) [MSC v.1500 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
ascii cp1256
ط³ظ„ط§ظ…
سلام
>>> s3 = 'سلام'
>>> s4 = u'سلام'
>>> s3
'\xd8\xb3\xd9\x84\xd8\xa7\xd9\x85'
>>> s4
u'\u0633\u0644\u0627\u0645'
>>> print s3
ط³ظ„ط§ظ…
>>> print s4
سلام
>>> s = u'Русский текст'
>>> print s
Русский текст
>>> 
'''

After applying serhiy.storchaka's patch:

'''
Python 2.7.5 (default, May 15 2013, 22:44:16) [MSC v.1500 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
ascii cp1256
ط³ظ„ط§ظ…
سلام
>>> s3 = 'سلام'
>>> s4 = u'سلام'
>>> s3
'\xd3\xe1\xc7\xe3'
>>> s4
u'\u0633\u0644\u0627\u0645'
>>> print s3
سلام
>>> print s4
سلام
>>> s = u'Русский текст'
Unsupported characters in input
'''

My point is that printing s3 and s4 in interactive mode, should produce the same results as printing s1 and s2 from source file. Loewis's patch handled this as I expected. Also this patch solves my problem of not being able to print u'Русский текст' (that is due to my Windows locale being set to Persian, not Russian.)