These steps are kind of low-level and can be automated using, for example, NetworkManager on current GNOME 3 distributions. However, here are lower level instructions that should work across a wide variety of Linux distributions and versions:
Step 1: Get the usb0 internet connection working fine on the box that's directly connected by USB to the phone.
Step 2: Plug in the ethernet cable between the computers.
Step 3: Use the following commands on the host computer, as root, or wrap in sudo:
ifconfig eth0 192.168.0.1 (or choose your own IP address within the designated LAN IP segments
ifconfig eth0 netmask 255.255.255.0
Step 4: Use the following commands on the client computer (the one that doesn't currently have an internet connection), as root, or wrap in sudo:
ifconfig eth0 192.168.0.2 (the first three numbers should be the same; the last one should be different, from the private IP of the host computer)
ifconfig eth0 netmask 255.255.255.0
Step 5: Adapted from here, execute these steps as root or wrap in sudo on the host computer:
echo 1 > /proc/sys/net/ipv4/ip_forward
/sbin/iptables -t nat -A POSTROUTING -o usb0 -j MASQUERADE
/sbin/iptables -A FORWARD -i usb0 -o eth0 -m state --state RELATED,ESTABLISHED -j ACCEPT
/sbin/iptables -A FORWARD -i eth0 -o usb0 -j ACCEPT
If you have existing settings (such as whatever Firestarter did) you may have to flush your iptables on the host, before executing step 5:
iptables -F
You can check your existing settings using
iptables -L
Finally: You probably already have a private IP address on a LAN from your usb0 connection. You may not use the same IP subnet for your NAT on the eth0 NAT. So if your usb0 has 192.168.0.10, you can't use anything from 192.168.0.x on eth0 on either computer.
Linux usually decides routing based on the interface metric.
Look at 'route -n' and see what it says. If you have one default gateway (0.0.0.0) with a higher metric, that one will be preferred over all the others.
I'm honestly now sure how linux chooses to route if all the gateways are the same--but the point is that you need to give one default gateway a higher metric.
It's been a while since I've touched Network Manager, but I believe there are settings in there for what metric to give the gateway.
Worst case you could use the 'ip route' command to remove and re-add a gateway with a different metric. For example:
ip route del 0.0.0.0/0 via 1.2.3.4 dev eth0
ip route add 0.0.0.0/0 via 1.2.3.4 dev eth0 metric 1
Best Answer
As I was using the Networking utility in Ubuntu to configure my Network Connections the settings in /etc/network/interfaces are apparently ignored.
When I right-click on the network icon then Edit connections -> eth0 -> IPv4 Settings I cannot Apply the settings without a Gateway set. Yet on the dialog opening from the Routes button I can tick the "Use this connection only for resources on its network" box. This will prevent the route from getting added and I can still access the internet through my other connection.