Interesting question. I was about to launch in to my usual - do this with either webforms, or Views, CiviEntities, VBO etc but knowing that the VBO interface is not 'great' for general users I wondered what could be done via multiple record fields and profiles.
You hadn't specified if you were thinking of using Civi Relationships, though the word is in the subject. But I don't think civi can give a user access to edit their own relationships particularly easily.
A Webform could be the solution since it does allow you to manage your start / end date etc so may be worth exploring more.
ANyhow, on demo site (which will of course be refreshed within 24 hours and lose this set up) I set up a multiple record field set with 2 types of 'employer fields' in case Contact Reference would be an option too (seems not from my testing based on the existing permissions for 'demo')
There is also a profile set up with this used for View/Edit
So now if you go to
you will see the fields, and the user can Edit and Add new records to these fields.
Not sure how close this gets to answering your question since it does not use the Current Employer field, and does not use civicrm Relationships.
But i thought I would go down this route as I need to familiarise myself with what is now possible with multiple record fields in the newer versions. ;-)
Also noting that the Contact Reference field works fine in the civicrm tab on the contact record eg for http://d46.demo.civicrm.org/civicrm/contact/view?reset=1&cid=202 but not when it is used in a Profile which may be a well known limitation but just mentioning it here in case it might just be permissions or less likely a regression