It sounds like you have done almost everything to get your brakes working, I suspect that the forward/backward thig is more perception that real. Peds are easier to push forward anyway.
Ped brakes are "single leading shoe" brakes, which means they exert the same braking force going forward or backward. "Double leading shoe" brakes are the ones that don't work going backwards.
On to your problem. I wonder where the shiny black comes from on your shoes. Abresive action on steel, which is what your brake drums are lined with, does create black stuff. But it does not sound like you have had enough braking action to do this.
Have you cleaned the inside of the drum and the shoes with brake cleaner until a paper towel comes away clean?
If this is true, then the only thing left is pad shoe material. I don't know what you have done so far, you may have to refresh me.