How does "Phone" app show information of contacts that are not on the address book?

I believe Android's native phone app is using Google's place search API. As you can easily search for a place by its phone number and get place details like name, place id, formatted_address and many other fields that you can find in the documentation

Request URL: https://maps.googleapis.com/maps/api/place/findplacefromtext/json

Request method: GET

Request query parameters:

• key: Your application's API key.
• input: The text input specifying which place to search for (for example a name or phone number).
• inputtype: The type of input. This can be one of either textquery or phonenumber. Phone numbers must be in international format (prefixed by a plus sign ("+"), followed by the country code, then the phone number itself).

Example request: https://maps.googleapis.com/maps/api/place/findplacefromtext/json?input=%2B972035283487&inputtype=phonenumber&fields=place_id,name&key=API_KEY_HERE

Example response:

{
   "candidates" : [
      {
         "name" : "מלך העופות",
         "place_id" : "ChIJ78ko1zBKHRURpwbgUdWc4nU"
      },
      {
         "name" : "Of Yaakov",
         "place_id" : "ChIJv3myn4FMHRURUGffcXgxKuw"
      }
   ],
   "status" : "OK"
}

Note: Such an API is not available at the current moment in Google places SDK for Android, but you can use the HTTP API directly in your app or you can make an API in the backend as a proxy to the places API. I prefer the later version as in the first solution the API key is deployed in the application code and hackers could decompile the APK and use it for malicious reasons. For security reasons you have to restrict the usage of the API key to the IP address of the server in case you are using the backend solution!