This is a good question but hard to answer. I search the origin of the character for you.

Shi 師 originally means "many people" 人眾 in traditional Chinese. In Shuowen Jiezi 《說文解字》, an early Chinese dictionary, Shi 師 refers to two thousand and five hundred people (二千五百人爲師). It seems that Shi 師 as army division appears earlier than Shi 師 as teacher.

But I don't know what's the relationship between the two usage.

Hope that helps.