So, the question is: Should I be calling unregister_netdev from the
notifier callback?
Not really, as you saw it can be deadlock prone.
One idea is to run the unregister asynchronously via a workqueue.
That should be able to get you out of the deadlock.