Here is a very general, abstract construction. Let $X$ be an incomplete seperable inner product space and let $Y$ be its completion. Since $X$ is incomplete, there is some $y \in Y \setminus X$. If we had $y \perp X$, this would imply (by density) that $y \perp Y$ and hence $y = 0\in X$, a contradiction. Hence, $y\not\perp X$. Thus, by renormalizing, there is $x_0 \in X$ with $\langle x_0, y\rangle =1$.
Now, the function $\varphi : Y \to \Bbb{K}, x \mapsto \langle x, y\rangle$ is a bounded functional on $Y$ and thus restricts to a bounded linear functional on $X$. Let
$$
M := \{x \in X \mid \varphi(x) = 0\} = X \cap \rm{ker}\,\varphi
$$
and note that $M$ is closed in $X$.
Furthermore, $M \subset \rm{ker}\,\varphi$ is dense. Indeed, let $z \in \rm{ker}\,\varphi$. Then there is a sequence $(x_n)_n$ in $X$ with $x_n \to z$. Hence, $\varphi(x_n) \to \varphi(z) = 0$. Now let $x_n ' := x_n - \varphi(x_n) x_0$. Then $x_n ' \in M$ and it is easy to see $x_n \to z$.
Now, choose a countable dense set $(m_n)_n$ in $M$ and orthonormalize it using the Gram Schmidt procedure, producing an orthonormal set $(x_n)_n$ in $M$ with
$$
\overline{\rm{span}(x_n)_n} = \overline{\rm{span}(m_n)_n} = M.
$$
Here, we take the closure in $X$. Note that the above is indeed true (we don't get all of $X$), since $M$ is closed in $X$. Thus, $(x_n)_n$ is not an orthonormal basis of $X$.
But $(x_n)_n$ is complete in your sense: Since if $x \in X$ satisfies $x \perp x_n$ for all $n$, then (by density) $x \perp M$. But as saw above, $M$ is dense in $\rm{ker}\,\varphi$, so that $x \perp \rm{ker}\,\varphi$ (where we consider $x$ as an element of the completion $Y$).
But it is easy to see $\rm{ker}\,\varphi = (\rm{span}(y))^\perp$, so that (recall that $Y$ is complete) we get $x \in ((\rm{span}(y))^\perp)^\perp = \rm{span}(y)$. Since $y \in Y \setminus X$ and $x \in X$, this implies $x=0$.
One can now certainly make this construction concrete by choosing e.g. $X = \Bbb{K}[X]$ and $Y = L^2([0,1])$ or $X = \ell_0$ (the finitely supported sequences) and $Y = \ell^2$, but I leave this to you as an exercise.
Best Answer
Suppose that $D$ is your orthonormal set. You can define $$M = \overline{\mathrm{span}\, D}$$ so that $M$ is a closed subspace of $H$ and finite linear combinations of elements in $D$ are dense in $M$. That is, $D$ is a complete orthonormal set in $M$. Now write $$H = M \oplus M^\perp$$ and let $D'$ be a complete orthonormal set in $M^\perp$. You will need the axiom of choice for this, in general. Then $D \cup D'$ is the set you are looking for.