The information you have given is really to limited to provide any quality recommendtion without discussing a lot of possibilities. Any difficulties you are going to have will relate to a few different things. How deep is the existing sand? Do you also use live rock in your tank, and if so how much? How long has the sand been in the tank? If your sand is shallow and you have live rock in any substantial amount then removing all the sand at once likely will not cause a lot of problems. Shallow sand would not likely be providing a huge amount or proportion of your tanks nitrification if you have appreciable amounts of live rock. If you choose to remove the rock and fish, then the easiest way would be to siphon a great majority of the water out into a large trash container, remove the rock, then remove the fish. Then remove and keep the rest of the water down to the sands level. Remove the sand. Depending on your preference as to placing the rock on the bottom or on top of your sand. Put in the new rinsed sand, part of the water, the rock, most of the rest of the water, then the fish, followed by the rest of the water and as much new water as needed to fill the tank. All while trying to keep the cat away from the fish and every thing the same temperature. If you have a deep sand bed and little live rock, it is all a different story.