Batch Update Relationships
This is possible in one of two ways:


Use the API CSV Import GUI extension.  This will allow you to import relationships with start/end dates.  As a matter of workflow, you'll probably end up exporting existing relationships and reimporting via the extension.
Make the changes directly in SQL, in the civicrm_relationship table.


There's actions to add relationships between contacts and a household/organization in the search action menu, but what you're describing doesn't exist out of the box.  I certainly think it's a good candidate for a sponsored improvement though.