Here’s a bit of an offbeat request.
I’m putting together a playlist of songs about mysterious, dangerous strangers.
Examples I already have include:
- Dangerous Stranger by Be Bop Deluxe (of course!):
Strangers In The Night? 
I’m not sure I understand it well enough to know whether it fits, but maybe Bob Dylan’s Man in the Long Black Coat?
Riders on the Storm by The Doors.
The Man Comes Around by Johnny Cash.
Ronnie James Dio - Don’t Talk To Strangers - - YouTube
BLACK SABBATH - No Stranger To Love -
Deep Purple - Perfect Strangers - YouTube
The first thing that springs to mind for me is Leonard Cohen’s “The Stranger”.
For a really dangerous stranger there’s another Nick Cave song called “The Kindness of Strangers” off his Murder Ballads album.
Oooh, some great examples here! Thanks, and keep 'em coming!
Thudlow Boink, “Man in the Long Black Coat” is exactly the sort of thing I’m looking for. 
AC/DC - “Night Prowler”
You can’t get much more dangerous than the first verse ofVehicle, by the Ides of March.
Tom Waits, “Black Wings” (maybe not exact, but it came to mind)
Shooting Star, “Last Chance”: Last Chance - Shooting Star (lyrics) HD - YouTube
“And the stranger said to them / I have been upon the mountain / I have witnessed forces like cannons that can ram you to the ground”
Ayreon, “The Stranger from Within”: Ayreon - The Stranger From Within - YouTube
“He’s a stranger / I don’t know where he’s coming from / Is he a danger to me or just another man?”
Dead Kennedys - The Prey.
Cowboy Junkies - Floorboard Blues
Look under his floorboards, Mama / I don’t trust his silly grin / He’s got a beat-up Rambler, Nebraska plates / And I ain’t getting in
Rolling Stones: “Midnight Rambler”
Moon over Bourbon Street, by Sting.
The first thing I thought of was Eurythimics’ ‘Love is a Stranger’. Maybe that isn’t exactly what you’re looking for–
–but ‘Missionary Man’ might be.
‘The Disillusionist’ from The Church’s song of the same name may or may not be a stranger, but he’s plenty strange.
Or like half the songs off that album. “Song of Joy,” “Where the Wild Roses Grow,” etc.
Marty Robbins - Big Iron (best known of late from Fallout: New Vegas)
Toadies - Possum Kingdom. I don’t think anyone knows what it’s about, but the narrator is menacing.
Kompressor - Never Talk to Strangers (maybe not :))
Blackjack David - Dave Alvin cover of a traditional song.