JackLacavasummarized your option well. I have reorganized some large (~5,000 members) UD hierarchies recently and did it by modifying the XML manually (Notepad ++). Here are my steps that can be modified for your situation:
1) Use Excel to create the relationship lines to move base entities to temp parent and load.
<relationship parent="Temp_Parent" child="Base1" aggregationWeight="1.0" />
2) Export relationship metadata to be replaced. Add Action="delete" to each relationship and load back into OS. This should remove the old hierarchy, while keeping the base members in a temp location.
<relationship parent="Old_Parent" child="Base1" aggregationWeight="1.0" Action="delete"/>
3) Load new hierarchy
4) Remove relationships under the Temp_Parent member direction in the dimension hierarchy.
5) Delete "Temp_Parent" member