It's good that you are able to recognize the grammatical concept of possession and not just assume that "of" will always correspond to a genitive in Latin. However, in this case it is just the same thing as if we were to say "He is a man of great wisdom". This is a genitive describing characteristic, not the usual possessive meaning. You can also have an ablative of characteristic as you suggested with "vir magna sapientia", but this is more common with physical characteristics than intrinsic qualities.
flebile nescio quid queritur lyra, flebile lingua murmurat exanimis, respondent flebile ripae