I highly recommend to combine this with the level 99 and/or 99.999.999Gil achievements if you did not
got this in your story playthrough.
If you always use and hold your Materia in your Weapon or Armor Materia slots, this will definitely come on "Disc 2" or "Disc 3" by the nature of the game. You can also use Double growth weapons (and alter triple growth) to speed this up.IF NOT:
The easiest and fastest way to obtain this is defeating the Magic Pot in the Northern Crater. You have to feed him an Elixir and then defeat him for a whooping 8000XP and 1000AP. Some times they come in two.
Another good spot for leveling and farming AP are the woods around Mideel.
To speed this up you can use double AP weapons for every character and also one tripple AP weapon for Cloud and/or for Cid. There are no armors with tripple AP but 2 and 4 slot Double AP armors.
Clouds Apocalypse can hold 3 Materias and have Tripple AP this weapon can be found in the Ancient Forest very late in the game.
Cids Scimitar can hold 2 Materias and have Tripple AP. The weapon can be found in Underwater Reactor, this is part of the Huge Materia Side Mission and the weapon is Missable.
The Platinum Bangle have 2 Slots and Double AP and can be bought in Costa del Sol for 1800Gil
The Rune Armlet have also Double AP and have 4 Slots it can be bought in Bone Village for 3700 GIl
I recommend to use the "All" Materia. Regular you will found one or two along the way. They can also be bought in Fort Condor later in the game for 20.000Gil. If you master a Materia they "Reborn". This will give you a new Level 1 Materia for free. The "All" Materias need 35.000AP to Master.
If you level up with Magic Pots i recommend to use the W-Item Materia. You can found this in the Sector 8 Tunnel raid on "Disc 2". You have to go the tunnel all the way to the south even if the characters say this is wrong. Alternative you can dig this later out in Bone Village. You can duplicate as many Elixir as you like, if you have a minimum of two. With W-Item equipped take one Elixir. Take another and with
to "stop" using it push
again and so on. Every time you duplicate one up to 99.
Here is a video solution for this.
(Video credit goes to 19HajimeSaitou91)
Level 4 Limits are not needed and i highly recommend not to fight alone in the North Crater.
Edit: Added more detail.