Вобщем если кому интересно - могу написать, к какому решению я пришел.
UPD. Решение такое:
1. Использовать $ionicViewService.clearHistory для очистки истории навигаций внутри ion-nav-view.
Когда я в своем примере перехожу на шаг 1, то в соотв. контроллере в самом начале я чищу историю, при выходе с шага 2 в другую вкладку я тоже чищу историю. Сервис определяет, какой именно стек чистить, по видимым вьюхам.
2. Не использовать href в ion-tab. Он их обрабатывает как-то по-своему, для того, чтобы активировать вкладки.
Т.е. если написать href="#/tab/common/state1" и в табе было ранее когда-то активировано состояние state2, то активируется этот таб и будет отображено state2, хотя просили state1.
Если сделать $state.go('tab.common.state1'), то отобразится state1, но только тогда, когда таб уже активен! Это вытекает из третьего пункта.
3. Deep Linking с табами не работает. Т.е. если на холодную запустить приложение с url #/tab/common/step1, который отображается во второй вкладке, то ничего не произойдет, потому что при запуске будет активна первая вкладка. Тут вот чувак с тем же самым столкнулся
https://github.com/driftyco/ionic/issues/2442. Я решил этот вопрос в лоб, повесив на сами табы контроллер, в котором исходя из текущего состояния вручную активирую нужную вкладку через $ionicTabsDelegate.
P.S. Поведение, как у меня в примере, которое меня не устроило, является корректным, вот заводской пример
codepen.io/ionic/pen/odqCz