I can see what you mean. For the Deutsch problem, we can formulate it (or think of it) in such a way that the goal is to evaluate $f(0)+f(1)$ in base 2. Classically we have to evaluate $f(0)$ and $f(1)$ to get this sum, so we need to do two evaluations of the function to get the answer. A quantum computer only needs to input the superposition state $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ once and it gets enough information about what the black box function does to $|0\rangle$ and to $|1\rangle$ individually, in order to be able to evaluate the sum modulo two successfully.
But a classical computer can parallelize the evaluation of $f(0)$ and $f(1)$.
Are there quantum algorithms that provide a speed-up without this type of parallel evaluation of a function for all possible binary-string inputs?
Well there's an entirely different type of quantum computing called "adiabatic quantum computing" or AQC which does not involve gates or circuits. There's a mathematical proof that it is equivalent to circuit-based quantum computing in terms of computational power, from the perspective that AQC devices can simulate all circuit-based quantum computing algorithms with an overhead which is only polynomial scaling with respect to the size of the problem.
In AQC, you are solving a problem by efficiently finding the ground state of a Hamiltonian which is $2^n \times 2^n$ in size if there's $n$ qubits. In the case where the Hamiltonian is diagonal in the computational basis, this problem can be parallelized by just checking each possible state in the computational basis, in parallel. However when the Hamiltonian is not diagonal, the only way to solve the problem (in general) on a classical computer is to find the eigenstate with the smallest eigenvalue, which means solving an eigenvalue problem. The solving of an eigenvalue problem can be parallelized but not in the way that I think your question is considering. It is not the type of parallelization where we are checking $2^n$ things at the same time, and the speed-up due to parallelization is nowhere near the quantum speed-up. Then since circuit-based quantum computers can also simulate adiabatic quantum computers with overhead that only scales polynomially with respect to the input size, we can argue that circuit-based quantum computers can also solve problems that can't be parallelized (in the sense discussed earlier) on a classical computer: in fact we've had circuit-based algorithms for Hamiltonian simulation since before we knew about the proof that AQC and CBQC were equivalent from a computational complexity perspective.
Essentially, if you want to find the ground state of a molecule's Hamiltonian, or the ground state of some model condensed matter Hamiltonian (for example) like a Hubbard Hamiltonian, quantum computers (or quantum "simulators") can do the job more efficiently (from a computational complexity perspective) compared to classical computers, and while classical computers can attempt to solve the problem in parallel, that parallelization is only whatever small amount of parallelization is possible when solving eigenvalue problems.
I don't know if there's any classical computation worth doing on a quantum computer that cannot at all benefit from parallelization because even the multiplication of two scalar numbers like 13.254621 and 17.169920 is parallelized at some level (for example multiple logic gates in hardware are working in parallel), but if we can interpret your question as parallelization in the Deutsch problem sense, then I would say that the answer is yes.
