I know how to add new pokemon without replacing, well almost exactly. You will need to repoint every single table that deals with your pokemon. From dex entries, to sprites, even to footprints, and expand them to hold the new information. Then, i believe there is a location in the rom tht determines how many pokemon are in your game, but I might be wrong.
You could just use the empty slots that come after celebi, the only problem with them is that they don't have dex entries, so the game will crash trying to load them if caught in the wild. However, they work find if you use them for extra evolutions and pokemon that are given to the player, but not caught.
In my opinion, it would just be easier to replace an old crappy pokemon and theb just reorder the pokedex using PGE.