Zidane can be removed from your party in Memoria, or whatever the place is called.

And Freya isn't the only character with a 9999 attack. Zidane's Thievery skill gains damage the more you steal. Quina's Frog Drop gains damage as you catch frogs in the minigame. And Steiner's Shock ability triples his damage I think, so that's basically 9999 everytime.