Is TrustZone mandatory on all new ARM CPUs? i.e. are they required to implement TrustZone?
No.
If not, what vendors implement TrustZone and which don't?
That would ask for a list and be a reason to close your question. You have to look on line and do research. Often vendors are secretive and will only answer some question under NDA. It depends. So, if a list existed at the current time, it will quickly become outdated. You can see supported boards and vendors at Trusted Firmware for an incomplete list.
What does implement mean, exactly? Is it the same as supported/compatible? I guess all newer Cortex-A CPUs support it, but some may not implement it. I suppose if it is not implemented / only supported, it means that the CPU starts in the 'secure' world but does not change to the 'normal' one?
Support/compatible is whether it will honor the bus signalling of the NS bit. So, the CPU needs to know nothing about TrustZone, but the bus signals from the core allows it to exist in a TrustZone system. ARM is both 'HDL' (hardware description language) and a software CORE company. The distinction is probably only of use to someone at an SOC company integrating the ARM CPU.
Implement means it actually does the TrustZone stuff (bus signaling and the CPU). It does not mean that the chip is secure for all applications. SOC vendors must work to integrate peripherals/devices to work for different security applications.
Also, a particular core may implement TrustZone, but an SOC vendor can handicap it so that it is useless.
Finally, from an ARM64 Linux distro running on the 'normal' world, how can one check if the CPU implements TrustZone?
This is previously asked. Nothing changed. The goal is that this should not be available. There maybe ways for some systems, but not generically.