With the stock motor I'm sure you'll get at least a half hour run time with that battery. My brother and I have been running cheap 3500mah ebay batteries and even with modified motors we get about 20 minutes.
The reason I'd suggest nihm over lipo is cost and complication. With Lipo batteries you need a special charger, and an ESC that will cut off the power before the battery gets too low. With nihm just about all hobby grade chargers these days will charge them and you don't have to worry about low voltage cutoffs. Get that battery and look up the Duratrax Piranha Digital Peak ac/dc charger. It's a good decently cheap charger that will charge the nihm battery you stated. You can use it by plugging it in the wall or a 12v car battery.
BTW the reason I say to get nihm over nicd is because you can only get nicads up to 2400 mah. The larger the mah the more run time. So you have the choice of getting multiple nicads or one nihm. It'll probably come out to the same price, but with nicads you'll have to keep switching out packs every few minutes.