The Story HD battery has 2 cables. Not many possibilities there.
As for the connector, it's great if you can solder them, but with wires it can be done without. Nothing a bit of duct tape can't handle.
This picture here
http://openinkpot.org/attachment/wik...ry/Com/pcb.JPG looks like the story also has just a 2 wire connector battery. The connector itself is different from the Story HD, but the battery itself looks pretty much the same.
Maybe something like this could be suitable: but I can't guarantee it
http://www.reichelt.de/MP3-Player-Sm...9;GROUPID=4351