Here is how you can obtain Level 4 Key Spheres. It might be possible to obtain them from chests or as prizes in side-quests, but these are the main ones:

Steal: Nemesis
Drop: Seymour Flux, Spectral Keeper, Omega Weapon, Land Worm
Bribe: Chimera Brain
Stealing from Nemesis provokes a counter (Ultima), so you probably don't want to get them that way. Seymour Flux, Spectral Keeper and Omega Weapon are bosses you can only fight once, and two of them you have to fight at a particular point in the game. Land Worms can only be found once you are past that 'point of no return': if you're like me, you wouldn't want to wait until just before the final battle. That leaves the bribery.

One other option would be to bribe Master Coeurls, or steal from Nemesis to get Warp Spheres. You only need one Warp Sphere per ability, the other characters can use Friend or Teleport spheres to get to the ability after the first person has.