Dont do drastic things like that. Nitrates kill a lot of stuff, but your animals are used to it. A 100% water change would be worse than not doing anything at all, namely, the shock of a NO3
free environment would kill off most of your animals. Do a small water change, approx 25%, and then add some live sand. You want the deph of your sand bad at at least 2-3 inches of fine sand, but not sugar sand, that one tends to be sucked up a lot durring water changes. Finally, when you have done all of this, I would suggest lowering the feeding for a little while. You also might want to look into a better skimmer, or just improving the function of the current one. Doing all of those things will slowly and safely bring the levels down. Just take it easy, and slowly fix the problem. You dont want to shock the little animals.