Yeah, I was going to mention Randy Newman, but others beat me to it.

As for Steve Earle, I don't know about "John Walker's Blues"; I think that was an attempt at something different. But some of his other material certainly fits the profile. One of my favorites is called "All That I Can Do," which sounds at first like your basic love song, until you realize that it is basically written and sung from the standpoint of a stalker (You say you're gonna call the cops/But I ain't gonna run/'Cause you're the only one/And there ain't no way I can live without you, etc.).

Another person worth mentioning is Richard Thompson; some of his work is positively chilling, and he makes no attempt to sugar-coat it or add in a moral. For a good example, listen to "The Uninhabited Man"; spooky.

Personally, I think this can be some of the best songwriting there is. It's relatively easy to write something that echoes all the platitudes we've been taught about how we're supposed to behave; it's much harder, it seems to me, to write from inside the mind of a criminal or degenerate, and show how much that person has in common with the rest of us.