SSL certificate selection based on host-header: is it possible?

Historically, your first statement is accurate. Now, there are multiple options:

A wildcard certificate if subdomains within the same domain.
A SAN/UCC cert to specify alternative names for the certificate, thus being able to serve multiple certificates.
SNI was introduced to establish the SSL connection after the Host header. This has limited support, however, as it is newer.

This has been answered numerous times on ServerFault by myself and others. I'd suggest searching for further details unless you have a specific question.

To extend Warner's answer: CAcert's page Vhost Task Force compares several methods for using multiple domains on a single server. I personally use Server Name Indication.

Short answer: no

HTTP is encapsulated inside SSL, so any information about the request is inaccessible until the connection has been established. Hence until a certificate was given to the client. No way to use headers nor any other encrypted info, as they are still not available.

EDIT: this is true if you want nowadays to be cross browser and fully portable. As said by others there are some new emerging methods making it possible in the near future.