If the phone will work with an ad-hoc connection, you could add a wireless adapter and share it with Internet Connection Sharing.
If not, there are a few wireless adapters that will work in master mode (as an access point). Asus sold a motherboard with one on-board, but I don't know of any others off the top of my head.