I am trying to understand the concept of an Ehresmann connection on a fibre bundle $B$.
Am I correct in saying that the connection gives the decomposition of every vector in $TB$ into the sum of a vector in the vertical bundle $VB$ and a vector in the horizontal bundle $HB$ (at the same point in $B$, of course)?
Does the projection onto the vertical bundle not exist until the horizontal bundle is defined, even though the vertical bundle is defined without the connection?
Yes, this is correct. The questions you're asking are on the level of vector spaces, rather than at the level of fiber bundles.
So suppose I have a direct sum decomposition $T = V \oplus H$. This means that there are subspaces, $V$ and $H$ in $T$, such that every vector $t \in T$ has a unique decomposition $t = v+h$, these vectors living in the respective subspaces. Also at the level of vector spaces, if I have a vector subspace $V \subset T$, there is no obvious way to get a projection map $T \to V$ that's the identity on $V$. But if we have a subspace $H$ with $T = H \oplus V$, then we can write $\text{proj}_V(v+h) = v$. That is to say, we just need to specify the kernel of the projection to define the projection. So, conversely, given a projection, we can identify what the horizontal subspace is by saying "Ah! It's the kernel!"
So at the fiber bundle level, you're just doing this pointwise, such that the horizontal subspace varies smoothly. That is, the projection (defined above) of any vector field $\text{proj}_V X$ is smooth.