How can I effectively remove the coating from woodless colored pencils?
I wish I could test this personally but I do not have those pencils. Have you tried plastic or steel wire brushes? 



Image from Amazon

The steel(metal in general) ones might remove too much material. This could largely depend on technique. So the plastic one might be effective but so much as to remove too much material. You can keep the pencil on the "table" and run the brush up and down the length. Then rotate to get to the other side. 

I would have suggested sandpaper or fine steel wool (#0000) but that requires more handling that risks breaking.

The way you could make that work though is to take a piece of wood and cut it so that there is a channel that would perfectly fit the contour of the pencil. Also have to be short enough so that you can hold the pencil at each end.



If you were to glue some fine sandpaper to this block you can then work the pencil inside it.