>"Teacher of gods and men" sounds better to my ear
>than "teacher of gods and humans".

Agree. "Gods and men" is a standard pair phrase in English, bringing to mind ancient Greek mythology and the like. 'Humans' sounds like it belongs in a show on the nature channel about primates. The two words just don't fit together, since they come from such different stylistic contexts. But if we wanted to insist on avoiding the word 'men', perhaps 'human beings' would work a bit better than just plain 'humans'.

/Rett