For users, the key is normally derived from their password. It's delivered out of band in the same way that a sysadmin usually delivers users their initial passwords (paper, phone, insecure email, etc).
For services, the key can also be delivered out of band (e.g. by SFTPing a keytab file over SSH or downloading it over HTTPS), or by using an admin's Kerberos credentials to authenticate to the KDC admin service – e.g. Active Directory joins are done by creating the machine account over a Kerberos-authenticated (and encrypted) LDAP session.
Kerberos also has the 'PKINIT' extension which changes the initial AS step to use X.509 certificate authentication instead (together with DH key exchange); this shifts the initial trust problem elsewhere.