If the site already exists in Matrix, then setting up the new site structure could be tricky considering that children come along with parents. Any changes you make to the structure will happen on the live site as well.
Your best option is to copy the live system and set up a whole new Matrix system on the same box. Then, you can go nuts restructuring, designing and running long HIPOs. When you want to switch, just change the Apache aliases and it happens instantly. Also, you can always flip back if you stuff up overlook anything.
I probably do the redesign and the restructure separately.
If you're working with a live site, you can apply your new design to the existing site as a user defined code, then you can view the design using SQ_DESIGN_NAME=code.
In terms of the restructure, it depends on the size of the site, and the complexity of the restructure. If you can get away with restructuring individual pages at a time, i'd do that. Otherwise, I suppose you could link your new structure into a new site, then change the URLs as suggested.
Either way, you will want to use the remap manager to manage redirects from your old to new urls.