The fact that it flickers on the TV but not your phone could be due to a few things.
The refresh rate of your TV may not be set to 60 Hz (USA, 50Hz for Europe). It should be, but sometimes this setting gets nudged.
The small size of your screen may cause the video to be subsampled. The big screen should show every single pixel in its original form. Therefore, the smartphone may be masking the problem.
This could also be a compatibility issue. TV sets won't play every single video format in existence, and if you feed it something that it can play, but which is at the edge of what it can keep up with, you can get artifacts. Usually this is stuttering, but perhaps it could strobe.
If you can post a 5-10 second sample that has not been re-rendered, I can tell you more.
P.S. As you probably know, there is a an "anti-flicker" option in under the settings icon in the camera setting dialog. It is usually set to "auto," but perhaps you can get better results by setting this manually.