After some tinkering I've come up with a proof which is still not the one I am hoping to find (if there is one at all), but it is closer to what I need in the sense that it is obviously generalizable to the multidimensional case, it is reasonably short, and it (kind-of) only relies on the very basic definitions of the gradient/derivative.
We start by defining a function $g(\mathbf{h}): \mathbb{R}^n \to \mathbb{R}$ as follows:
$ g(\mathbf{h}) = f(\mathbf{x} + \mathbf{h}) - f(\mathbf{x}) - \nabla f(\mathbf{x})^T\mathbf{h} - \frac{1}{2}\mathbf{h}^T\nabla^2f(\mathbf{x})\mathbf{h} $
It now remains to show now that $g(\mathbf{h})$ is $o(\Vert\mathbf{h}\Vert^2)$.
Note that $g(\mathbf{0}) = 0$, $\nabla g(\mathbf{0}) = \mathbf{0}_n$ and $\nabla^2 g(\mathbf{0}) = \mathbf{0}_{n\times n}$. Then $ \frac{\nabla g(\mathbf{h})}{\Vert\mathbf{h}\Vert} = \frac{\nabla g(\mathbf{h}) - \nabla g(\mathbf{0})}{\Vert\mathbf{h}\Vert} \to \nabla^2 g(\mathbf{0}) = \mathbf{0}, $ and consequently $\nabla g(\mathbf{h})$ is $o(\Vert\mathbf{h}\Vert)$. Next, repeating the same step for $g(\mathbf{h})$ we have that $ \frac{g(\mathbf{h})}{\Vert\mathbf{h}\Vert} = \frac{g(\mathbf{h}) - g(\mathbf{0})}{\Vert\mathbf{h}\Vert} \to \nabla g(\mathbf{h}) = o(\Vert\mathbf{h}\Vert), $ which implies that $g(\mathbf{h})$ is indeed $o(\Vert \mathbf{h} \Vert^2)$. Substituting $o(\Vert \mathbf{h} \Vert^2)$ instead of $g(\mathbf{h})$ into the first equation, we obtain the necessary result.
Now this is still not simple enough, to my mind, and there should be something better and "more obvious".