After two days of frustrating research, after installing every multilingual plugin I could find and fail to do what I wanted, I finally found Multi-Language Framework.
I find it amazing for version 0.1. It is very intuitive, smart built, easy to work with and it simply does the job. It was a very pleasant surprise that it works fine with WordPress 3.5 while other plugins fail to do that.
Great job guys! Thanks!