Hell is a region, and for most large-scale places English uses the preposition "in" to describe location.
I am currently living in the United States.
She is sightseeing in Hollywood.
He is the tallest man in the U.K.
"On" is used for more specific locations that (more or less) you can physically be on top of
She is standing on Hollywood Boulevard.
He is on the corner of Hollywood and Vine.
I am on the observation deck of the Empire State Building.
Of course this idiomatic expression is metaphorical, since whoever they are, they didn't actually come from Hell. It just implies that they look like something that you might find in Hell, were you to visit.