Technically, Agility isn't new on Shedinja, but this is the first it's been able to get it in a while. In Gens 3 and 4, if you evolved Nincada at a level at which Ninjask learned a move, and then let it learn that move, the resulting Shedinja would get it as well. And it was perfectly possible to do this at the level on which Ninjask learned Agility, so Shedinja's been able to get Agility.