There have been many, many threads on this subject in the past.
To summarise, get at least 4 high quality AA batteries (one to use, one to charge/store); they must be PHOTO grade (referred to as "Photo" or "Digital" on packaging), at least 2500NiMH. I have Duracell ones and Fujicell ones, 2650NiMH and 2700NiMH respectively. Any NiMH recharger is fine, if they are a trickle charger leave them for about 24 hours to charge, if the recharger cuts out (green light goes on) after a while (mine at about 3 hours), then put them back in again to top up. Never use alcaline batteries, waste of time, as you would have got in your pack with the system, for the reason you discovered.
Yes, the batteries will get a little warm, this is normal, due to the power the GP2x drains from the batteries; if they are getting hot, you need better batteries as they can't cope. With a good set of batteries you should get a couple of hours or so between recharges.
A good source for batteries and chargers is e-bay; cheaper. Avoid generic batteries or Chinese/Hong Kong sellers, unless the batteries state they are made in Japan (not China). If you don't, you may get low grade batteries which are fine for normal applications but NOT for the power hungry, battery sapping, GP2x.