No levitation or water walking? A wand of cold with sufficient charges can be a last resort if you need to cross the water on Medusa's Island. The bolt will freeze any square of water that it crosses. You can use this to build and extend ice bridges. Try to use the shortest bridges possible. Even if you only had one wand, you might still make it, even if you have to wrest that last charge by repeatedly zapping the empty wand. If you have a frost horn, you can use that instead. Be careful of monsters with fire attacks, though!
If you need to use the wand of cold to reach Medusa's down staircase, then zapping a wand of digging downward is a superior idea. You might even choose to zap down to the Castle, as Eidolos does in the ttyrec about the drawbridge. You could collect the Castle loot and the wand of wishing and come back up with better equipment. Or you could even go down to Vlad's Tower for the guaranteed water walking boots.
Wands comprise 4% of all randomly-generated items in the main dungeon, 6% in containers, 5% on the Rogue level, and 8% in Gehennom. There is a 4% chance that a randomly-generated wand will be a wand of cold.