Good possibility that they are fill rock. The coating appears to be similar to iron oxide like hematite and may be present due to chemical interactions with the environment and some form of extreme heat. I usually see stones like that in the desert southwest, thats why I asked where you see them, that have a similar patina on the sunny side of the stone. Such rocks have a high iron content and in the desert the extreme heat and occasional moisture create the affect your picture shows. It can be pretty neat to pick one of these shiny black rocks up to find a lily white bottom.