http://tuxmobil.org/ is a great place to start.
Don't be too hard on Verizon, right now I'm typing with a laptop tethered to the internet through my Treo 700p and through the Verizon 3g network. OMG, suddenly all these people are following me (Gee I hope you got the joke). Seriously, let us know if you have any success. My Treo is also old and I am looking for a new phone, and I'd like to try installing Linux on this one after its been replaced. One thing that's a must on a new phone, a usb port that allows tethering, the usb sticks, from what I hear aren't as fast.