The classical proof that the halting problem is undecidable is extremely flexible and applies to innumerable non-classical models of computability.

The argument goes like this. Suppose that we have a notion of computability, by which a program $p$ on some input $x$ leads, when halting, to an output $y$. The halting problem is the question of determining which pairs $(p,x)$ do in fact lead to an output $y$. Suppose within this system we had a way to compute this. Then consider the following process. Design a "program" such that on input $q$, it determines whether $q$ halts on input $q$, and if so, our algorithm does the opposite. Now, if our algorithm is implemented by program $p$, then $p$ halts on $p$ if and only if it doesn't, a contradiction.

The argument applies to any model of computability that is able to implement this process, and this includes numerous instances: computability on Turing machines, register machines, oracle computability, polynomial-time computability, infinite time computability, and on and on and on.

Any abstract notion of computability that has sufficient universality ("run program $q$ on input $q$") and nontrivial branching ("do the opposite") capabilities will be able to implement the algorithm, and will therefore have an undecidable halting problem.

Meanwhile, let me mention that for some models of computability, the various versions of the halting problem that are equivalent in the classical computability context become inequivalent. For example, in ordinary Turing computability, it doesn't matter whether you describe the halting problme as the membership problem of the set $\{p\mid \varphi_p(0)\downarrow\}$ of programs that halt on trivial input or as the membership problem of the set $\{(p,x)\mid \varphi_p(x)\downarrow\}$ of program/input pairs that halt; it doesn't matter because these two sets are reducible to one another and have the same Turing degree. But the analogous fact is not true for all models of computability. For example, the theory of infinite time Turing machines, where one has two jump operators, corresponding to the lightface and the boldface halting problems, and these are not infinite-time computably equivalent. A similar situation arises in higher recursion theory.

The classical proof that the halting problem is undecidable is extremely flexible and applies to innumerable non-classical models of computability.

The argument goes like this. Suppose that we have a notion of computability, by which a program $p$ on some input $x$ leads, when halting, to an output $y$. The halting problem is the question of determining which pairs $(p,x)$ do in fact lead to an output $y$. Suppose within this system we had a way to compute this. Then consider the following process. Design a "program" such that on input $q$, it determines whether $q$ halts on input $q$, and if so, our algorithm does the opposite. Now, if our algorithm is implemented by program $p$, then $p$ halts on $p$ if and only if it doesn't, a contradiction.

The argument applies to any model of computability that is able to implement this process, and this includes numerous instances: computability on Turing machines, register machines, oracle computability, polynomial-time computability, infinite time computability, and on and on and on.

Any abstract notion of computability that has sufficient universality ("run program $q$ on input $q$") and nontrivial branching ("do the opposite") capabilities will be able to implement the algorithm, and will therefore have an undecidable halting problem.

Meanwhile, let me mention that for some models of computability, the various versions of the halting problem that are equivalent in the classical computability context become inequivalent. For example, in ordinary Turing computability, it doesn't matter whether you describe the halting problme as the membership problem of the set $\{p\mid \varphi_p(0)\downarrow\}$ of programs that halt on trivial input or as the membership problem of the set $\{(p,x)\mid \varphi_p(x)\downarrow\}$ of program/input pairs that halt; it doesn't matter because these two sets are reducible to one another and have the same Turing degree. But the analogous fact is not true for all models of computability. For example, the theory of infinite time Turing machines, where one has two jump operators, corresponding to the lightface and the boldface halting problems, and these are not infinite-time computably equivalent. A similar situation arises in higher recursion theory.

Finally, let me mention the theory of infinite time register machines, which approaches an example of the phenomenon that you request. These machines extend the operation of ordinary register macines into transfinite ordinal time, in a way analogous to the infinite time Turing machines. Nevertheless, it turns out that for the ITRMs, there is no universal machine, and indeed, this is a consequene of the fact that for each finite $n$, the $n$-register halting problem for ITRMs is in fact ITRM decidable. (One needs more than $n$ registers to do it.) This phenomenon definitely does not occur in the classical finite time theory, since once one has sufficiently many registers, the model of computability is fully powerful for classical computability. For the infinite time theory, however, adding more registers continues to make the model of computability stronger, with the halting problem for the smaller machines becoming decidable by the larger machines.

The classical proof that the halting problem is undecidable is extremely flexible and applies to innumerable non-classical models of computability.

Given a notion of computability by which a program $p$ on some input $x$ leads, when halting, to an output $y$, the halting problem is the question of determining which pairs $(p,x)$ do in fact lead to an output $y$.

  Suppose within this system we had a way to compute this. Then consider the following process. Design a "program" such that on input $q$, it determines whether $q$ halts on input $q$, and if so, our algorithm does the opposite. Now, if our algorithm is implemented by program $p$, then $p$ halts on $p$ if and only if it doesn't, a contradiction.

The argument applies to any model of computability that is able to implement this process. Almost any true notion of computability is indeed able to do so, and indeed, we might take it as a criticism of any supposed concept of computability unable to implement this idea, that it strains the meaning of computability.

One key ingredient, of course, is that the model needs to be able to treat programs as input (and otherwise the halting problem makes no sense anyway).

In this way, the undecidability of the halting problem applies to innumerable notions of computability: computability on Turing machines, register machines, oracle computability, polynomial-time computability, infinite time computability, and on and on and on.

Meanwhile, one can certainly construct artificial notions of computability, for example, by trivially modifying primitive recursion, so as to satisfy your stated requirements. And perhaps someone will post a more genuine example.

The classical proof that the halting problem is undecidable is extremely flexible and applies to innumerable non-classical models of computability.

The argument goes like this. Suppose that we have a notion of computability, by which a program $p$ on some input $x$ leads, when halting, to an output $y$. The halting problem is the question of determining which pairs $(p,x)$ do in fact lead to an output $y$. Suppose within this system we had a way to compute this. Then consider the following process. Design a "program" such that on input $q$, it determines whether $q$ halts on input $q$, and if so, our algorithm does the opposite. Now, if our algorithm is implemented by program $p$, then $p$ halts on $p$ if and only if it doesn't, a contradiction.

The argument applies to any model of computability that is able to implement this process, and this includes numerous instances: computability on Turing machines, register machines, oracle computability, polynomial-time computability, infinite time computability, and on and on and on.

Any abstract notion of computability that has sufficient universality ("run program $q$ on input $q$") and nontrivial branching ("do the opposite") capabilities will be able to implement the algorithm, and will therefore have an undecidable halting problem.

Meanwhile, let me mention that for some models of computability, the various versions of the halting problem that are equivalent in the classical computability context become inequivalent. For example, in ordinary Turing computability, it doesn't matter whether you describe the halting problme as the membership problem of the set $\{p\mid \varphi_p(0)\downarrow\}$ of programs that halt on trivial input or as the membership problem of the set $\{(p,x)\mid \varphi_p(x)\downarrow\}$ of program/input pairs that halt; it doesn't matter because these two sets are reducible to one another and have the same Turing degree. But the analogous fact is not true for all models of computability. For example, the theory of infinite time Turing machines, where one has two jump operators, corresponding to the lightface and the boldface halting problems, and these are not infinite-time computably equivalent. A similar situation arises in higher recursion theory.