You can buy extended life batteries for most phones, which double the life of the battery. They come with a replacement cover; the normal battery cover can't be used, because the batteries are about twice as thick and stick out of the phone.

It makes the phone thicker, but that's a price worth paying. I have one in my HTC Desire Z, and I had one in my G1 before that. They're surprisingly cheap. On the scale of about $15. I had three of them for my G1, so I had no problems going camping for a week, and not having access to a charger.