He is outside and near the coast. I did that quest a while ago, and it took me forever to find him.
If you go from the Locksmith out the gate on that side of town, you want to run almost straight out the gate to the coast. He will be a little to the south, but almost directly east. I wish I still had my map from when I did that quest. I'll have to take a look and see if I can find it and post it to my website.