Internet Connection Sharing works in Ubuntu.

You want to have your Ubuntu box connected to the Internet via the USB
port, and provide a gateway to the rest of your LAN via Ethernet, right?

The "Firestarter" firewall contains an Internet Connection Sharing
feature in its setup wizard. It works well for me.

I have static IP addresses assigned to all of my local computers'
Ethernet ports. I've set up the "client" computers to use the
Internet-connected computer as a gateway. I've also had to provide
the client computers with explicit DNS addresses.

Your setup isn't quite the same as mine, but I'd bet that
"Firestarter" would be a good place to start.