I'm a bit confused about your definition of "rechargeable battery"... AA and AAA format NiMH rechargeables may not be as small as proprietaries, but they sure are much easier to come by...
For instance, the Canon A460 or the one of the older A530 and above are quite small and powerful. You have a viewfinder as well as a screen... and they are quite capable - the SD storage format is probably the cheapest and widespread, too...