Translation:All three of Matěj's wives had brown hair and green eyes.
I'm right there with you! And your first suggestion would get my vote.
UPDATE (Nov 2018) - I've also added "All of Matej's three wives..." In a sentence like this, while the "All X# of (something countable)" construct is used most often, "All of X# (something countable)" gets a fair amount of use as well. Ngrams
Isn't it covered by this grammar rule?:
We often use of after all in definite noun phrases (i.e. before the, possessives and demonstratives), but it is not obligatory:
-All (of) the workers were given a pay-rise at the end of the year.
-I gave all (of) my old books to my sister when she went to university.
-What shall we do with all (of) this cardboard? Throw it out?
Anyway, I am changing the default.
All three of those examples are perfectly correct. But this particular sentence just sounds very weird without "of."
And, now that I think of it, I just wrote "All three OF those examples" without even thinking about it. Maybe there's a rule -- that we native English speakers know but don't KNOW that we know -- that says "of" has to be used with a number or "quantity" word.