Re: "only way to transfer your contacts from an old iPhone to a new one is via the cloud"
Local password protected backup -> restore new iPhone from local backup has worked every time for me. No need for cloud, and all the same contacts are present with no need for a cloud backup for this case at least.
Now iCloud is useful to keep multiple devices in sync, but even then there's no reason why this cannot be just a per-user backup rather than being data-mined and combined with other users' contacts, which I suspect was Tim Cook's comment.