Headhunter

Currently, there is no way to obtain player heads in Survival without mods. Yet, this feature is highly sought after and available in Creative via commands. There should be a way to get player heads in Survival, but it should also not be too easy.

I present to you: The headhunter.

The headhunter is a humanoid mob, maybe similar to the Wandering Trader in appearance but more Wild West style. It would spawn in the mesa biome, maybe in a special structure such as a saloon, maybe just out in the wild.

When you meet the headhunter,you can order a player head by tossing him some gold (a nugget?) as down payment. The nugget can be unnamed or renamed to the name of a specific player. Once the headhunter takes the gold, it will head out and disappear.
Exactly one in-game day later, the headhunter returns. It will now trade the head it got once for one gold ingot. If the initial nugget was named, it will trade that player's head. If it was not named or the headhunter could not find a player by that name, it will trade a random head. If the game is offline, it will trade a random mob head.
Be quick, though: The headhunter will reset after another in-game day passes. Once a trade has been made or missed, the headhunter may accept a new mission.

That way, player heads become available in Survival while not becoming too common. The headhunter adds some flavor to the mesa biome and would fit neatly into the mesa update alongside tumbleweeds and vultures.