You're right to have doubts about the security of a four-digit pin code - whatever Apple does to protect your Keychain data, at least somebody within Apple would always be able to perform a brute-force attack for all 10000 possible digits with very little effort. It's simply not possible to protect against a parallel brute-force with such a low-entropy input, no matter what KDF you use.
Since the implementation is proprietary and closed-source, everything about the actual workings is speculation, so please take the following speculations with more than a grain of salt. That being said, here is how a service like iCloud Keychain could be implemented in a way that is consistent with Apple's public statements.
The Keychain contents really seem to be encrypted with a client-side symmetric key; probably only an encrypted version will be uploaded to Apple's servers.
Adding new devices probably happens via public-key cryptography (granting a "new device" requests could encrypt the symmetric key with that device's public), but unfortunately allows no fingerprint verification (which makes man-in-the-middle attacks possible, just like with iMessage).
The recovery password will likely be used to encrypt the symmetric key using a key hardening function using a salt and many iterations before it is uploaded to Apple; when using that recovery code, Apple probably uses a hash based on that code to rate-limit recovery attempts before handing out the wrapped symmetric key together with the encrypted Keychain data.
Ars Technica has an interesting article on the subject, and they come to the conclusion that using the suggested four-digit recovery code makes a brute-force attack very feasible - but only for Apple (or somebody who manages to break into their server-side infrastructure).
I've also written about this in a blog post myself, where I come to very similar conclusions.
To sum it up: If you're worried about Apple (or somebody who is able to gain access to their systems, whether hacker or law enforcement authorities) getting access to your Keychain data, use at least a strong alpha-numeric password for recovery or don't use the recovery code at all.
