One Option: The easiest way I have found (in 4.6.4) is to export like you said, with contact ID, do your manipulation in excel to pull out the records you would like to keep, and re-import the records into a group, choosing 'update' when you do so.
If you need to merge information, you could put it on the line with the contact ID you will be keeping.
Then you can grab all of the contacts in your group (or all contacts not in your group, depending on which way you selected) and delete them.
To export these contacts, search for all, select all, and choose 'action>export'.
The import tool can be found under 'contacts>import contacts'.
One thing I have found on our setup is if I import a large dataset (say, more than 10k records at a time) I will get a timeout and the import will stop with 'db error', which is frustrating, so I usually break these up into smaller sheets to import.
Another Option: I believe you can do this programmatically with the API if you are more comfortable doing that. I haven't used this approach though so I don't know how well it works.
Possibly related: Batch merge automation of big data set