Deustch algorithm using one qubit
Unfortunately, as D.W. says, it's not possible to do Deutsch's Algorithm with only a single qubit.

The key is the line you quoted in your question: the quantum oracle for the function $f$ returns $\mid x\rangle \mid y \oplus f(x)\rangle$. This only works with two qubits.

Why can't we just make the oracle return $\mid f(x) \rangle$? Well, in quantum computing, all functions must be reversible (you can reconstruct the input from the output), and we have no guarantee that $f(x)$ is reversible. And if we force $f(x)$ to be reversible, then we know it's balanced, and the problem becomes trivial (return "balanced" every time).

The only way to make a reversible function out of a function that may not be reversible is to add "ancillary" or "garbage" qubits; this is how the Toffoli gate implements the non-reversible AND function. That's basically what the second qubit is doing here: without it, we can't even necessarily call the function.