I would go with either a Lum Berry or a Quick Claw.
Lum Berry- The reason I say this is because the Toxic and Status conditions are the easiest way to kill this thing besides weather. With a Lum Berry, it at least allows you to shake off that status condition to see another turn. However, you will need an abundance of them to make it through the game
Quick Claw- Shedinja is rather slow so a Quick Claw may give you the chance you need to go first and attack. This could be the difference between a KO for you, or Shedinja fainting. Nluckily, this is obtained in the Trainer's school in Rustburo City.
Overall, I would go with the Quick Claw because even though it is more luck based, it will still give that boost you need(hopefully) to get that knock out. And you only need one Quick Claw, unless it gets knocked off. However, it is your choice.
Hope I helped!