Sparkfun sells low frequency (433 and 900mhz) RF transceiver modules but their power output is only in the 500mw range, good for maybe a few hundred to a thousand feet I'd guess roughly. GMRS might be an option but I'm not sure if there are any GMRS modules that are small enough to meet your needs, a typical handheld GMRS radio is about the same size as the Android option, I'm sure modules could be made but small formfactor radio options like that are a niche market, so most of of the modules you'll see will be cell phone network based.
Although I'm sure if you researched it enough and didn't mind spending the money you could develop something small enough for your needs, but for very small children the easiest option would be X harness with the device attached like a backpack, but that introduces some saftey issues of it's own, as you already know, half the problem is getting the kid to not lose the device in the first place =) Virtually impossible for younger kids, older kids it's a little easier because belt packs are more practical. But the little ones can strip themselves naked even if you shackle their clothes on it seems =)