Generally, off the top of my head is usually used to refer to the first thing that pops into your head.
What's the capital of Mauritania?---I don't know off the top of my head, but I could go and look it up.
This is a valid thing to say but you could also say:
I don't know off the top of my head, but it will come to me.
Meaning that it's not immediately available in your mind, but you do know the answer.
By heart implies something slightly different. To know something by heart it to know it inside out. You'd never hesitate to remember something you know by heart because you know it so well.
These are just my opinions and interpretations of the phrases (since you have already supplied the dictionary definitions).
However, given those slight nuances, I would lean towards using:
Our teacher was a really smart person. At the second session, he know everyone's name by heart.
...since your sentence seems to imply that he had picked them up really easily and knows them inside out, rather than just that that he had them in the forefront of his brain.