I've been thinking about this problem for a while. I think the solution is to let the TCP/IP stack in another computer (PC, Mac, Linux box) do all of the work.
Here's how it would work.
There would be a program running on a PC with network access. This program would talk to the USB serial port connected to your Arduino.
On the Arduino side, there would be a library that replaced the Ethernet library. Let's call it SoftEther, in honor of SoftSerial. This library would have the same functions as an Ethernet library.
When your Arduino sketch did a function call, for example, SoftEther.begin(), the SoftEther library would send a request to the PC via the serial port. The request would just contain the parameters from the begin() call. The PC would execute the necessary function calls and return any status via the serial port.
There are a lot of advantages to this approach. Apart from a PC, no additional hardware is required. You wouldn't have to worry about assigning an IP address (or implementing DHCP), since it's all taken care of on the PC side. Routing to the Internet would also be taken care of automatically.
There are lots of precedents for this approach. Firmata and RPC come to mind.
Of course, there are some downsides. It would tie up the serial port, which always makes debugging harder (although, you could add a debug print function to the library which would display a message on the PC). It would probably be a bit slower than a real Ethernet shield, especially for large amounts of data. Besides the library, someone will have to write and maintain the PC-side programs for the different platforms, although you could probably write it in Java (or Processing) and make it portable.
Any volunteers? :)