If it's out of warranty do it yourself instead of sending it to Apple. Many small shops can do it while you wait.

You can also get a battery kit online, includes the battery, instructions and the tools necessary. $18.00

here's a link http://www.digiexpress.us/Battery-kit-for-iPhone-3G_p_106.html