How to change encoding in Mail in OS X Mavericks?
It seems you're not the only one with this problem.

I found a KB article on Apple's website that clearly specifies that Message > Text Encoding should be available in the Mavericks version of Mail:

http://support.apple.com/kb/PH14955

It says "Mavericks" in the title and is current as of Nov 6, 2013.

I've filed a bug report letting the OS X team know.