Both your ideas are good, but why not have both? So you could either build a dog and try to deceive him, or just find the dog. In the case of you building the dog (when I say building an animal I mean something along the lines of creating llamas and farm animals) you would have to do something like roll for deception or add a new feature to the SPECIAL system, and if you fail the Old Coot provides a surprisingly tough fight. Or you could just find the dog with ways such as yours, but not trading microchips if there is no endgame gear and resources to make up for it. However, I still think there should be a quest based completely (or at least mostly) on luck.
Viewing post in Wasteland Stories!!! - Side Quest ideas and Suggestions
Okay, I like the idea of trying to decive him or either find the actual dog, and for a quest that is completely random could work, but if we are thinking of speedrunners, it would most likely be a turn off from the game. Now if there was a point of the game (like the second to last main quest) where you still haven't found what you were looking for - it would automatically be there, so you wouldn't still be searching for it for ages at the end of the game.