I think "Start Over" button will be better than other options. The current position of StartOver button is really clumsy. My suggestion would be to add refresh icon at the top (one right of the title) to start over.
You are right, the general rule is: stay consistent. On the other had, rules are there to be broken ;-) if there is a very good reason. This sounds like a good reason to replace the back button with a "Start Over".
To be sure, please test this! If users are really confused by this replacement, add a button to start over.
Since the back button has no preview option, the user should be able to easily get back to the item, if the back button does not meet his expectations. So if the hierarchy is really big, you should probably provide the user with a history of all his visited items, where he can easily go back to any item he visited.
If the user presses a notification and was ...