While I can't provide any answers as to the origin of the phrase, the meaning is closer to the latter than the former.
What the phrase is implying is that the subject possesses attributes or qualities that set them above an already superior group. For example, if the only differentiation between a Gentleman and a regular man was physical beauty (such that all gentlemen were handsomer than non-gentleman) to say someone was "a man among men" would imply that out of a group of handsome gentleman, who are, by our definition, already handsome, this person is so much more handsome than the rest that the other gentlemen appear plain by comparison.
It's a bit of a different question as to what qualities "man among men" is referring to as it relates to people, however.