Now that you beat the game you can do whatever you want! Once you are done with the Battle Tower, fly back to Mossdeep City. Go into the house to the left of the Psychic gym. You will see a Pokeball on the table and a note left for you. Inside the Pokeball you will get a new Steel/Psychic type Pokemon, Beldum. Now fly back to Slateport City, and enter that strange red house. You will see a small girl to the left. Talk to her to get your own Pokeblock Case, if you have not yet done so. With that, you can finally enter the Safari Zone! So fly back to Lillycove City and go west until you see a strange house. You will find many old Pokemon in there. Near the enterance you can find: Pikachu, Wobbuffet, and Girafarig. In the water you can find Psyduck, and by fishing you can find Goldeen and Seaking. With the Mach Bike you can find Pinsir, Ryhorn, Rhydon, and with the Trick Bike you can find Heracross, , Phanpy and Donphan. In each area (except water) you can find Natu, Xatu, Doduo, Dodrio, Oddish and Gloom. You can use the Trick Bike to jump across the pillars and the Mach Bike to go up the mud.
Now for some legendary catching. Fly back to Sootopolis City. Leave the city borders but explore underwater in the seaweed. You will eventually see a Pokemon named Relicanth It looks like a brownish fish with a red dot on it. Catch it. Then look for a Wailmer, and evolve it by leveling it up. Be sure to have Relicanth and Wailord on your team, and with someone that has Dig and Diving, fly back to Pacifidlog Town. Surf west, along the south. Allow yourself to get pulled by the currents. You will eventually reach a place were you can dive underwater, shown below. Once underwater, surf south untill you find a strange code on a wall. Look at it, then dive back up. You will find yourself in a strange cave. Go to the north code on the wall, and use Dig on it, to open it up. Then move Relicanth to be your first Pokemon, and Wailord as the last evolution. Then talk to the slate in the north. You will hear an earthquake. Now leave this cave, and lets start tracking down some legendarys!
That earthquake opened up some new caves, so lets start off by flying back to Mauville City. Be sure to have lots of Hyper Balls for this, as well as someone that knows Strength. Head north into Route 111, and enter the desert. Go as south as possible, until you see a strange cave, then enter. You will see a slate to the north, and talk to it. Now from that spot go 2 spaces east, then 2 spaces south. Now use Strength, and the cave should open. Go inside and you will see a large Pokemon. This Pokemon is the Rejirock, one of 3 Reji. They are all level 40, and know similar moves, like Ancient Power. Each one can be annoying, but its not too hard to beat. Take notice that their stats cannot be decreased due to their Ability, Clear Body. Once you catch this Reji, save and lets head to the next one.
Now fly back over to Petalburg City. Surf down along the ocean on Route 105, over on the west side of it. You will eventually find an island with some trees and a trainer on it. Land atop it, and start surfing on the other side of it, and then start surfing north. You will eventually find another cave similar to the one before. Enter the cave and talk to the slate. However, for this cave to open you must wait a few minutes after talking to it. Once it opens, you will find Rejice. Once you catch it, lets head over to the last one.
Now for the final Reji. Fly all the way back to Lilycove City. Go west to Route 120. Go up some stairs and continue north. You will pass some grass, and then it will start raining. You will find another cave like the ones before. Enter it, then talk to the slate. Go into the center of the room and use Fly. The cave should open, revealing the most difficult Reji, Rejisteel. Once you capture/beat it, pat yourself on the back.