Ok, acabei de descobrir que o Android tem o IP Forwarding desativado por padrão. Para ativá-lo, digite o seguinte:
sysctl -w net.ipv4.ip_forward=1
Os itens acima permitirão o encaminhamento de IP, mas ainda é necessário fazer mais:
iptables -F -t filter #Deletes all previous rules in filter table
iptables -P FORWARD ACCEPT #Allows IP forwarding
Agora, não sei se é uma boa ideia excluir as regras anteriores ou se é necessário, mas a boa notícia é que essas regras não são persistentes. Na próxima vez que você inicializar seu dispositivo Android, as regras serão revertidas para onde elas estavam. Isso também significa que você terá que repetir isso toda vez que inicializar o dispositivo.