I got this same vibe during the brief interchange between Jon and "Rattleshirt" before their little sparring match. "We all do what we have to do, Snow. Even kings." Based on the context, he was referring to Stannis when he said "kings," but there could easily be a double entendre here. I immediately thought of King beyond the Wall, not Stannis.
The only thing that keeps me doubting is that Jon does not seem to notice anything different about Rattleshirt other than his body build. I would think Jon would be able to notice something in his face (eyes, for instance) or even his voice. By the sound of the description, if Mance did indeed switch places with Rattleshirt prior to the execution, then he would have had to knock out quite a few of his own teeth to replace them with wooden ones.... Poor bloke.