30 minutes - 2 hours
I bought a used iPod Classic and got about 3 hours of music out of it (or ~40 minutes of video) on a full charge.
The swap was pretty easy once you get the right tools. It took around 20 minutes after I started to get the casing off to sealed back up. It has A LOT of clips on the inside, the advantage being it is pretty hard to actually damage anything.
Throw away the plastic tools they send with the battery, they are complete trash. I ruined both of them in around 2 minutes trying to insert them. Just get a thin putty knife (thin enough you can bend it by hand), with a width of around 2 inches or less. Insert a corner of the knife into the seam and work it down, wiggle the rest of the blade in and move it up or down to get the side clips. Insert a corner into the top next then the opposite side. The back cover should come off fairly easy after that. It goes back together TIGHT so don't be afraid to be firm with it.