Se o seu suporte android USB ethernet (rndis), você pode verificar este post . Leia a resposta do k.Cyborg.
Isso estabelecerá a ethernet virtual via USB entre o telefone e o laptop.
No laptop, você pode usar o script linux-router para facilmente encaminhar o dhcp e o nat do servidor.