Before plastic bags became readily available, reponsible dog owners either trained their dogs to pass motions on their own property, or on the street at the kerb edge. Some dogs owners, but very few, took a newpaper or a trowel with them when walking their dogs.
Dogs did not have to be kept on leads all the time when I was a child, so the problem was not so great, as most dogs found a suitable patch of grass (suitable in their eyes, rather than in ours).
I don't know about English towns, but in Scotland and Denmark the two countries where I grew up, shopkeepers and householders swept the pavement outside their house every morning - my paternal grandmother, who had lived in France until war broke out in 1914 hosed her pavement in the French fashion every morning, so dog dirt was not exactly a problem outside her house.
You could be fined for littering public streets, and as policemen walk their beat, this was no empty threat.
You can put up as many bins as you like, but that will not prevent lazy people from not depositing any kind of rubbish in them.
Changing the law and making it compulsory for anyone who acquires a dog, whether for the first time, or the nth time, to attend dog training classes with them, before a dog licence can be issued, and making it illegal to have an unlicensed dog works in Germany, where I have never seen dog dirt, either on city streets, or country roads, or discarded bags with the dirt. What I do see every time I cross the Danish-German border is well-trained dogs, that unlike their Danish counterparts, never jump up at you, as you pass them, because they are trained to sit, or lie down on the approach of anyone, and that if on a lead never bark at you. That a dog barks, as you pass the garden of the house it lives in, is only natural, but if the owner hears the dog barking, he or she will say something allong the lines of "that will do" and the dog stops barking, immediately.
