Water Shuriken is pretty gimmicky, imo. Without Skill Link, it's unreliable, especially without investing in Attack. It also doesn't do much to Talonflame, since he outspeeds you (Base 126 Speed according to Serebii), and ties with you for priority thanks to Gale Wings. Maybe on a dedicated physical Greninja it might work running something like Toxic Spikes/U-Turn/Water Shuriken/"Filler", but even then, the unreliable power on Water Shuriken is somewhat worrisome. Run Azumarrill if you want to take out those threats with a priority water move.
As for partners - I think it depends wholly on what coverage moves you choose. Below are the coverage moves, and what they help check:
HP: Fire - Steels
Grass Knot - Bulky Waters
HP: Electric - Gyarados, Tentacruel, Jellicent
Dark Pulse - Ghosts
Extrasensory - Tentacruel
Assuming Ice Beam and Surf/Hydro Pump are your primary coverage moves and will be on every set (note - there's no real reason you HAVE to run them, thanks to Protean), the key to choosing teammates is to choose partners who you otherwise cannot touch. Also important is that every set is going to have trouble with Fairy/Normal Special Walls/Sponges, so you're going to want to pack a strong physical/mixed sweeper to take them down.