Symbian OS used in Nokia S60 handsets and Sony Ericsson UIQ handsets uses UCS-2. UCS-2 would be very easy to support as it's a strict subset of UTF-16. I think we should focus on the library design first before deciding which encodings to include though.
The external encoding must be specifiable as a runtime selection. Agreed. One of the most important use cases I see for this library would be reading an external file that's encoded in a manner not known until runtime - e.g. an xml file. Having to specify source encodings at compile time wouldn't be useful. Specifying destination encodings at compile time does seem useful though - i.e Read whatever is in this file and encode it into UTF-16. The destination encoding would probably have to be known anyway to pass the data to APIs.
I would definitely encourage breaking the work up into smaller chunks. I think one chunk should be routines that, given a sequence of bytes, determine that possible encodings used to encode those bytes (looking at bytes used and any BOM that might exist). This could be overloaded/extended by users for XML and other formats that can explicitly define their encoding (e.g. the encoding attribute on XML declarations).