I.e. do really only I have the private key or do I have to trust that StartSSL (or any other provider) don't store it themselves?
I must admit I haven't tried StartSSL, but its FAQ suggests multiple mode of key generations for applying for a certificate. This may depend on the type of certificate.
The "Wizard" mode (FAQ#43) visibly generates the key pair on the server side. Although FAQ#44 assures you that they don't keep it, you're entitled to be suspicious. This isn't considered great practice, but this is probably for convenience.
Alternative methods normally used by CAs consist of generating a key pair on the user's machine and submitting only the public key as part of a Certificate Signing Request (CSR). A number of tools will let you save a CSR. This can also be done manually using OpenSSL, for example. In addition, a key-pair can also be generated in the browser (which will not send the private key out) and a CSR (or equivalent, e.g. SPKAC or CMRF).
The wording of some other questions is a bit confusing, but it suggests they can accept CSR or SPKAC requests.
FAQ#33 says "I created a private key instead of submitting my certificate request (CSR) for IIS server". Opposing creating a private key to submitting a CSR is a bit confusing, because you'd create a private key to create the CSR anyway. From the answer, it appears that you the private key has to be known at some stage by the StartSSL server ("Login to the StartSSL™ Control Panel and click on the "Tool Box" tab. Select "Create PFX File" and submit the encrypted private key, certificate and your password for the key."), which isn't great practice.
However, FAQ#51 "Can I submit a certificate request (CSR) for client certificates (S/MIME)?" seems to suggest it's also possible to do this without StartSSL needing to know the private key. ("The private key and certificate request are generated by either using the tag (Firefox) or activeX control (Internet Explorer)".) The limitations they impose in their answer is somewhat artificial. There's no reason in principle why one mode of application would be tied to a usage purpose for the resulting certificate.
Regarding one of your comments:
Like many, you're confusing PKI and SSL/TLS.
I'm not a massive fan of the PKI model myself, because of its imperfections, but thinking that making everyone use a Web-of-Trust model (a la PGP) is sufficient to improve things is somewhat candid.
By using a WoT model, you may indeed have a less centralised system (which sounds good), but that makes the whole system far more complex, and much more difficult to think of, especially for users who "just want it to work". The difficulty mainly comes from the fact that each node in your WoT need to be trusted for two different things: (a) who they are and (b) their ability to verify who their next node is.
Trusting someone's identity is one thing, but trusting their ability (training and integrity) to do something opens a completely different dimension. If you consider that big CAs, whose job it is to verify others' identity, can sometimes have difficulties doing so, expecting that from all members of your WoT seems rather ambitious. Even if you wanted to restrict certain abilities to certain members, modelling those rules would itself be difficult.
I use StartSSL and any time I want a new certificate I generate a Certificate Signing Request (CSR):
This generates a private key as well.
Then in StartSSL's control panel you skip generating the private key (button labeled "Skip »»") and submit the generated CSR instead on the next page. StartSSL will get the public key from the CSR (and ignore all the other information).
Using this procedure StartSSL will not get the private key, because it is not part of the CSR.
It's serversided and you don't have 100% assurance that they don't store your private key. It's as simple as that, you have to trust them, if you don't trust them you have to go elsewhere, but the problem will exist there as well.