Whoa, I would definately NOT pull your sand out with your setup. IMO, thats going to result in the death variety pack extravganza. Your tank will be totally thrown into start-up type cycleing again, and this time, the bacteria isnt going to have the luxury of massive surface area and varied flow rates and varying ammonia and o2 levels to quickly create nitch strongholds to keep your nitrogen cycle together. You also will likely find that you have inadquate rock surface area to support much if any useful NNR without your sand bed in the tank.
If you really wana get rid of your sand (even though its not the problem at all and provides many good bennifits), you need to take it out 1-2handfuls per week, NOT just remodel and pull it all out. Remember, that sand in your tank right now is responsible for about 85% (rough guess) of all the filtration that occurs in your tank right now.
But seriously, try some cheato before you go nuts here. I personally think it would be much cooler to JUST add the cheato and a light on your sump, and NOT change any water or mechanically remove any algae. Then take update pics of your tank every week, and we could all get to watch the effects of cheato on your water quality and algae. If after just one week you dont like it, then you can go back to doing whatever.
It would REALLY be an awsome thing to watch the improvements weekly, and shoot, if it hurts your tank in anyway, I will totally restock your tank for you with anything you want(provided its within reason) for free.
Your fish and other things will really thank you for it.