Having Strangers' Names in Caller ID Display
I use Current Caller ID and it seems to work ok, better if you let it connect with Facebook. It is not perfect but it will help out.

I also use Reverse Lookup. It is after the fact, but it does a good job. it will google the number and quickly add it to your phone book if you want. 

Neither are going to get you coverage all the time but it is the best I have found.