Henkin-style completeness proofs for intuitionistic logic

What you are looking for is a proof of completeness for intuitionistic logic in a constructive metatheory. When one turns constructive, even the notion of completeness varies according to how it is formulated. For example, saying that a valid sentence is provable is not equivalent anymore to saying that a consistent theory has a model.

By arguments of Gödel and Kreisel, a constructive proof of (first-order) intuitionistic completeness without further modifications is not possible since such a completeness result would entail non constructive principles. However, Veldman (1976) found a workaround to this, by introducing Kripke models with so called exploding nodes, which are nodes which are allowed to force $\bot$. Classically, one could always discard the exploding nodes without changing the forcing at the other nodes, but constructively, the change is crucial: the fact that a node is exploding or not might not be decidable. Veldman sacrificed the decidability of a node being exploding in favour of a constructive proof of completeness for intuitionistic logic with respect to the semantics of these modified Kripke models. The result is described in "An Intuitionistic Completeness Theorem for Intuitionistic Predicate Logic" (The Journal of Symbolic Logic, Vol. 41, No. 1, 1976, pp. 159-166).

Subsequently other proofs were found, for example one by Harrie de Swart: "Another intuitionistic completeness proof" (The Journal of Symbolic Logic Vol. 41, No. 3 1976, pp. 644-662). There is also a categorical treatment of such constructive completeness theorems in a joint paper of mine with Henrik Forssell: "Constructive completeness and non-discrete languages" (https://arxiv.org/abs/1709.05817), in which we also see what happens if one considers languages of arbitrary size and languages for which equality between the elements of the signature is not decidable. It is also established that the use of the FAN theorem (compactness of the Cantor space) in these constructive completeness results is unavoidable. The proof here is in essence a Henkin-style argument of building models out of constants (which is at the heart of Joyal's completeness theorem), and which avoids the non-constructive detours of the usual first-order version of the proof you sketched.

Henkin-style completeness proofs for intuitionistic logic are perfectly possible: instead of maximal consistent sets, you consider, for each formula $A$, maximal sets $\Gamma$ such that $\Gamma\nvdash A$; the collection of all such sets (for all $A$ together) will form a Kripke model, where the sets are ordered by inclusion ($A$ is ignored for the ordering). In this model, each point $\Gamma$ will satisfy all formulas from $\Gamma$, and it will not satisfy the formula $A$ with respect to which $\Gamma$ was maximal.

Completeness with respect to Heyting algebras is even more trivial: just as in any other algebraizable logic, you just construct the Lindenbaum–Tarski algebra. That is, for a fixed $\Gamma$, you take the algebra of formulas with operations given by the connectives, preordered by $$A\le B\iff\Gamma\vdash A\to B,$$ and then its quotient by the kernel equivalence relation $A\le B\land B\le A$ is a Heyting algebra in which the canonical assignment gives $\Gamma$ value $1$, and all $A$ unprovable from $\Gamma$ a smaller value.

There are some more issues with predicate logic, but I’m assuming from the question that you mean propositional logic.