Users can "Personalize" any site as long as that feature/permission is enabled. I'm not sure if that will let them mess with the order of navigation elements on the page, but maybe it would.
If personalization does not work in that regard, you can also try experimenting with different "Permission Levels" which let you create new groups like the standard "Contribute, Approve, Design, etc" groups. You should be able to get to this from the ribbon in the permissions area of your site. The problem with giving people permission to change the navigation is that the "Global Navigation" is global, so everybody would see those changes and your navigation would be all over the place all the time.
A third option would be to create some kind of customization to use lists or even the actual site navigation itself to generate a user-configurable navigation scheme.
Maybe more info is required here. Does each user have/control their own site, except for the deletion? If that is the case you should be able to just give them that permission and be done with it. Is it a real concern that people would be deleting sites, where you could not control this with some sort of policy or rule?