Other is in the status where it is in a coordination with one, which is a determinative and can readily functions as determiner in the construction one of the men.
Since this is a coordination, according with the general rule other should be able to stand on its own in this position giving other of the men, which sounds to me at best very awkward.
However, this kind of construction one or other of the men, though not common, is indeed found in text from famous writers and should be attested.
Moreover, cases where I observe this construction all involve a set of only two members rather than one with multiple members, which is indicated by Barrie England in his answer.
And there are other cases where a head noun is present such as one or other man of the twins, in which case other is an adjectival modifier from my point of view, which normally cannot stand as a fused head as one, just as explained in the answer of Brett Reynolds.
So I suppose that the construction one or other of the men is some kind of idiom, in which case other may be an alternant of another, which is a determinative and can occur in this function as readily as one can, or a fused modifier-head not commonly found elsewhere.
This is pure supposition and I do not have any further evidence.