Yes.
It will be convenient to introduce some jargon and notation. The notion of computing from an oracle gives rise to the preorder of Turing reducibility (or "relative computability," or similar), which we denote "$\le_T$." This in turn gives rise to an equivalence relation on decision problems: $A\equiv_T B$ if $A$ computes $B$ and $B$ computes $A$. The resulting partial order of $\equiv_T$-classes is called the (poset of) Turing degrees, and is generally denoted by "$\mathscr{D}$" or similar.
The properties of this partial order have been extensively studied. Some results include:
Given any nonzero (= not the degree of the computable sets) Turing degree $\bf d$, there is a $\bf\hat{d}$ which is incomparable with $\bf d$ (this answers your question).
In fact, any (nonzero) Turing degree is contained in an antichain of degrees of size continuum.
Every Turing degree is above only countably many degrees, so the "height" of the Turing degrees is $\omega_1$; in case $\mathsf{CH}$ fails, this means the poset of Turing degrees are "wider" than it is "tall" (and even if $\mathsf{CH}$ holds this is still a useful heuristic in certain ways).
The Turing degrees form an upper semilattice - given decision problems $A, B\subseteq\omega$, the join of their degrees is the degree of $\{2n: n\in A\}\cup\{2n+1: n\in B\}$. Moreover, this semilattice has no top element (because of the "relativized" halting problem, or Turing jump).
However, their exist Turing degrees $\bf d$, $\bf \hat{d}$ with no greatest lower bound. So $\mathscr{D}$ is not a lattice.
Moreover, nontrivial infinite joins never exist (Exact Pair Theorem): given an infinite set of degrees $D$, if $D$ is nontrivial (= does not have a finite subset $D_0$ such that $\forall {\bf d}\in D\exists {\bf d_0}\in D_0({\bf d}\le_T {\bf d_0})$) and ${\bf a}$ is an upper bound of $D$, then there is a degree ${\bf b}$ which also is an upper bound of $D$, and which is incomparable with ${\bf a}$; moreover, $\{{\bf d}: {\bf d}\le_T {\bf a}$ and ${\bf d}\le_T {\bf b}\}=D$.
If $A'$ and $B'$ are the halting problems of $A$ and $B$, and $A\le_T B$, then $A'\le_T B'$. This means the jump can be thought of as an operation on degrees, not just sets. It turns out this operation is definable just in terms of the partial ordering! This was an extremely surprising result; see these notes of Slaman.
The converse of the above bullet point fails extremely badly: the jump is extremely non-injective. For example, for every ${\bf d}\ge_T{\bf 0'}$ there is a ${\bf c}$ such that ${\bf c'}={\bf d}$, ${\bf c}>_T{\bf 0}$, and there is no degree strictly between ${\bf c}$ and ${\bf 0}$ (such degrees are called "minimal," with the more exact phrase "minimal nonzero" being a bit long to say).
The above is all about the global theory of the Turing degrees; people have also studied extensively the local theory of special subclasses of Turing degrees. The best known such class is the class of degrees of domains of partial computable functions, the c.e. degrees. Of course, the degree of the halting problem is the maximal c.e. degree, so in this context the answer to your question is “no;” however, given any c.e. degree which is not the degree of the halting problem or the computable sets, there is an incomparable c.e. degree. This is the Friedberg-Muchnik Theorem, and its proof was a precursor to the method of forcing in set theory.
Let me end by stating my favorite two open questions about the Turing degrees:
Back in the day both these degree structures were believed to be very homogeneous, with lots of automorphisms; the theme of pure computability theory post-1955ish, however, was quite the opposite: the Turing/c.e. degrees are structurally rich, with lots of definable subclasses, and in fact it is now believed that both partial orders are rigid. All that is currently known however is that the automorphism groups are at most countable.
Finally, having said that the answer to your question is “yes,” let me explain a sense in which the answer to your question is “no.” The only “natural” increasing functions on the Turing degrees which have been discovered so far are essentially iterates of the Turing jump. Martin conjectured that this holds for "reasonable" functions. Ignoring some subtleties around the notion of iteration here there are a few ways to make this conjecture precise, the two most common being the following:
(1) $\mathsf{ZFC}$ should prove that every Borel function which is degree-invariant and increasing is an iterate of the jump, at least when we restrict to some set of the form $\{{\bf d}:{\bf d}\ge_T{\bf c}\}$ (that is, "on a cone").
(2) $\mathsf{ZF+DC+AD}$ should prove that every increasing function whatsoever is an iterate of the jump on a cone - the point being that under $\mathsf{ZF+DC+AD}$ all functions are reasonably nice.
- This can be "$\mathsf{ZFC}$-ified" to the following (3) which is more ambitious in conclusion but more demanding in hypothesis than (1): "assuming appropriate large cardinals, every increasing function on $\mathscr{D}$ which is in $L(\mathbb{R})$ is an iterate of the jump on a cone," since large cardinals yield determinacy in $L(\mathbb{R})$. See this survey article of Larson for background on determinacy, large cardinals, and tameness properties.
Currently weak versions of Martin’s conjecture have been proved, although the full conjecture is still very much open.
Why wasn't this discovered between 1875/90 and 1935? (Or was it?)
The argument you sketch could not be discovered until one had a sufficiently formalized understanding of what "a recipe for computation" even means to be able to argue that there are countably many of them.
Such an understanding had been brewing slowly in the first decades of the 1900s, fueled mostly by foundational considerations -- but it doesn't really seem to have been until the 1920s that people began to seriously consider that perhaps they shouldn't be thinking in terms of "what is the way to do such-and-such?" but in terms of "is there any possible way to do such-and-such?" And before the latter question gets asked there is no real interest in getting all pedantic about what counts or doesn't count as "a way".
Best Answer
$\mathsf{PA}$ is vastly more than enough to prove that the halting problem is incomputable. $\mathsf{PA}$ is in fact massive overkill for the vast majority of theorems about natural numbers, or "finitary objects" (such as Turing machines, despite the infinite tape present in our intuitive conception of them) more generally.
Meanwhile, in some sense $\mathsf{Q}$ is too weak a system for the question to be meaningful. There is very little which $\mathsf{Q}$ can prove at all - e.g. it cannot prove that every number is either even or odd (= $1$ less than an even number), nor can it prove that addition is commutative. Among other things this means that intuitively-trivial modifications to definitions often wind up resulting in inequivalent versions "over $\mathsf{Q}$." For example, I don't believe that $\mathsf{Q}$ proves that $2$-tape Turing machines are no stronger than $1$-tape machines. At this point it's not clear that the question means what we want it to.
Here's a sketch of why the incomputability of the halting problem goes through in a very weak system of arithmetic. (There are various versions of the halting problem; I'll use $\{e:\Phi_e(0)\downarrow\}$, where $\Phi_e$ is the $e$th Turing machine in the standard enumeration and "$\downarrow$" means "halts," for simplicity.)
The proof boils down to basic logic + a machine construction: given a machine $\Psi$ we need to define an auxiliary machine $\hat{\Psi}$ to "defeat" $\Psi$ as a putative halting problem solver. This $\hat{\Psi}$ behaves as follows: on input $e$ it simulates $\Psi(e)$; once (if ever) this simulated computation halts, $\hat{\Psi}$ goes into an endless loop if the result is $1$ and otherwise halts and outputs $0$ (say).
So all we need is a theory of arithmetic capable of proving that the construction $\Psi\leadsto\hat{\Psi}$ actually "makes sense." Since it's an explicit construction this boils down to a totality claim, and at a glance knowing that polynomial functions are total should already be enough. So we get all the way down to theories of bounded arithmetic, which form incredibly tiny fragments of $\mathsf{PA}$.