I think Both sentences are correct, however 'on the edge' is much more common in this instance.
'On the edge/edges of society' is talking about outsiders, or people not quickly accepted into the heart of society. In a way they are literally on the edge (the outskirts of mainstream society).
'On the Verge' is often used in a much more metaphorical way. It can often mean at the very start of something, as if teetering on the edge.
Eg. 'She was on the verge of tears'
They are very close but as a general guide I'd use 'on the edge' for more literal meaning and 'on the verge' for being at the start of something or one thing close to becoming another, or shifting into another state