Best approach would be to use some powershell script which will first create a lookup column in list (say A). 

Then iterate through items in list A and query list B to for specified value. Add this value to lookup and update item.

Based on the number of items you can do performance upgrades to the script: store IDs of items from list B in cache to avoid querying for the same items twice (or more).

There is already a question/answer how to create lookup fields with powershell: http://sharepoint.stackexchange.com/questions/97521/create-lookup-field-powershell