I have tried reading wiki carefully and translating these to a couple of languages, but it still eludes me. Is one editing, doing the technical stuff, while the other is the entity or person who decides what to publish?
There is probably not one totally correct differentiation between Verleger and Herausgeber because things may vary a bit between environments. However, here is what came, based on living in this language community, first to my mind:
Verleger: Person who runs (and usually owns) the business and is economically responsible for the publication.
Herausgeber: Person who is intellectually responsible for the publication (that however contains works from other persons than himself).
A Herausgeber is typically a societally distinguished person. The ordinary editor (Redakteur) is not called a Herausgeber, although of course what he or she does is intellectual work, too.
Probably most famous case: Helmut Schmidt, former chancellor of West-Germany, was presented (and known) as Herausgeber of "Die Zeit" (weekly paper). He wasn't however occupied with the economical aspects of the business.
I myself worked for some years for a daily newspaper in Germany whose Verleger (here: owner of the family business) was also his own chief editor (Redaktionsleiter), and could well have been called Herausgeber, but wasn't. People in the city saw him as the Verleger. For them, the fact that he owned the company, was more important than the intellectual work he did (which most of the citizens there anyway did not understand, I suppose).
"Verleger" is the person at a publishing house who decides which manuscripts to purchase, which authors to contract etc.
"Herausgeber" is generally the person responsible for producing the publication. For instance, if a collection of articles, short stories or the like from different authors is published as a collection the person who puts them together is the "Herausgeber". For a newspaper, the "Herausgeber" has the final say on what goes to print or steers it in a certain direction.
Often if there is a "Verleger" it will also be the "Herausgeber" but this is not necessarily true vice versa.