I finally finished this quest last night. Both shrunken heads are found in treasure chests. One in the lair at the Palazzo Laterano and the other out in the country, I think in the Antico district. Buy a treasure map of that district to help locate it, though it might be a Noble chest, so you'll have to have renovated most of the art merchant shops for it to be available for purchase.
I ended up with quite a few Indian diamonds, which I found from looting Borgia couriers and the bandits who randomly attack Ezio around the city. I think there are a few in treasure chests too.
But honestly, the shop quests hardly seem worth all the trouble they require. The inclusion of this little mini-game befuddles me.