Keith Packard maintains an excellent "picolibc" that I have used recently (and contributed to, a little). It was formerly called newlib-nano, and consists of newlib with the string functions replaced with cheaper (slower) versions from avrlibc and various other slimming changes (e.g. reduction of struct reent stuff, and some locale stuff, by default).
[1] http://sourceware.org/newlib/