Собственно, при подключении к Ubuntu Android телефона в режиме Internet модема соединение и так работает «из коробки». Если автоматическое соединение вас устраивает дальше можно не читать. Меня интересовал случай, когда требуется тонкая настройка соединения, например, указание дополнительных маршрутов или согласованная работа нескольких проводных соединений.
Network Manager позволяет настроить ручное соединение и привязать его к сетевому интерфейсу телефона. Сделать это не сложно, однако, проблема в том, что привязка осуществляется только по MAC адресу, а мой телефон меняет этот адрес при каждой перезагрузке. Способ обхода этой особенности оказался несколько неочевидным, поэтому публикую его здесь, может кому-то пригодится.