After looking at avr-libc, I've decided that it won't work either. There are a lot of assembly modules in there, as well as several modules which are hardware-dependant, all of which would have to be removed for the library to be of any use.
I could make a new library using all the relevant parts of avr-libc, but it uses a modified BSD license, which I would have to maintain for any extensions I made later. I don't have a problem with the BSD license, and it's probably the right one to use, but I don't want to deal with legalisms at this point.
Months earlier, I started working on my own libc implementation. At this point, it looks like my best bet is to just complete that project and call it a day.
By the way, there is some nice documentation on the libc functions at http://nongnu.org/avr-libc/user-manual/modules.html. That could be very handy for coverage checks.