Take the fish out and put in a 5g bucket with an airstone, as mentioned. Fill the bucket with tank water.
Gravel vac your gravel a bit, getting a lot of the mulm into a bucket with the water. Drain the top of the water off and save the slimy bottom layer.
Empty (most of the) water. Remove all of your old gravel.
Dump that nasty gunk you syphoned out onto the bottom of your tank.
Put all of your new gravel in.
If you want to be extra sure (and why not, it doesn't hurt), get a nylon and fill it with some of your old gravel and tie it off. Place that on the new gravel and leave it for one week.
Use the old tank water that the fish are in, and put it back into the tank, along with the fish. If the tank is larger than 10g, try to save more of the original water. 50% is good. Add that back to the tank. The reason for saving all that water is to not shock the fish by putting them in a tank with 100% new water.
That will get you through with no problems
Yes, though, you will need to remove the fish. It will get pretty yucky in the tank.