The day I got my Android phone, I discovered that the address given to it by my DHCP server in my wireless network was correct, but the phone still would not access the Internet. The only way I could access the Internet is if I set the IP configuration statically in the phone, which was a pain because I'd have to enable and disable static configuration every time I came home / went away.
Digging a little deeper -- using The Google a lot -- I discovered the problem was the phone itself -- if the phone requests an address via DHCP, and the reply contains a classless route definition (DHCP option 121), then the phone sets that up as the routes but never sets the static route correctly, and as a consequence the phone simply fails to route traffic outside the LAN. This is a known bug in Android, that hasn't been addressed in years.
Disabling this behavior was a two-step process with dnsmasq (my DHCP server of choice):
# Identify android devices dhcp-mac=android,AA:24:59:77:42:* # Disable classless static routes for Android dhcp-option=android,121,0.0.0.0/0,10.254.102.1
The first option in the configuration file lets me identify the Android phone as tag android. The second option sends an explicit "default route" using classless routing, effectively overriding the more general classless routing I am sending to the other machines.
This solved my problem. I can now browse the Web without having to set up my phone as static IP.