Ok... Ive looked around a bit and I think the best way to do this would be to use MCEdit, a out of game program that allow you to do mostly everything. Its a map editor.
There are 2 options:
1- Clean the griefed and ugly areas of the world and leave the towns where they are atm and expand the world of 1000 or 2000 more blocks.
(This option means that the new features of the latest update like the new trees and lapis will only be found in the newly generated 1000 or 2000 radius wide area)
2- Copy and Paste the currents cities and areas over a newly generated world. That would mean that the ressources would be found everywhere, but the location of your city would change, as the whole world map.
(This option is also very more time consuming and complicated because you would have to specify the areas i need to save.)
Since i cant make polls in a thread answer, please vote on the following topic:
http://minetown.net/forum/m/672632/viewthread/462607-world-clean-up