You're right. Under normal circumstances, genderless Pokemon can't get egg moves, as egg moves are passed from the male Pokemon, but Shedinja is by no means normal
Shedinja evolves from the Gendered Pokemon Nincada, which also evolves into Ninjask, which also had gender. Obtain a female Nincada/Ninjask, breed it with a compatible male (in the Insect group), and you have yourself a Nincada with the breeding move you desire. Then, evolve it it into Ninjask and Shedinja, and you will have two Pokemon with this breeding move, one with gender, the other without.
Basically, Shedinja gets egg moves despite being a genderless Pokemon because it evolves from a Pokemon with gender. However, as it is genderless, it is unable to pass on any moves, except those to an Nincada that it would learn by level up, and can only breed with ditto. Hope this helps.
