He appears at the Tomb of Oedon battling Eileen the Crow provided you have started her questline prior to opening the Hunter Chief Emblem gate in the Cathedral Ward.
(Trigger could possibly be the Vicar Amelia fight, or at least gaining the Insight from first encountering the boss, but other players have reported being able to start this NPC fight simply by speaking to her at the chapel after opening the gate without encountering Vicar Amelia at all.)
At the point in the game this fight occurs, Henryk is a considerable threat to you and Eileen even as a pair, and great care must be taken to defeat him without turning Eileen aggressive via friendly fire.
Henryk wields a Saw Cleaver and Hunter Pistol, and based on the stats of his unique gearset has a considerable resistance to Bolt, and a reasonably high HP pool, comparable to that of later NPC combatants such as Old Hunter Djura.
When defeated he drops the Heir Rune (Can't remember which magnitude) and Blood Echoes (How many?). His equipment set (links required) will be available for purchase from the Bath Messenger Insight for [insert set and prices here].
If Eileen is defeated by him with or without player assistance he will remain at the Tomb of Oedon indefinitely (Perhaps not after Rom/Red Moon/Paleblood Moon triggers) thus disabling the lantern until defeated.