You need the crystal. "on chip oscillator with caps" means that the chip has everything needed except the crystal. RTC chips that don't need an external crystal are pretty blatant about claiming "internal crystal."
Is the CAT24C512 compatible to the AT24C512?
It is extremely likely that they are compatible.
Usually, the alphabetic characters at the beginning of a part number identify the manufacturer of a chip. AT was Atmel, CAT was probably Catalyst Semiconductor (which was acquired by OnSemi in 2009.) Usually if you have a part with a "well-know"
"suffix" part number ("24c512"), there will be pretty good compatibility, especially when it comes to digital parts with less room for variations. Occasionally, less so.
(Like, an ATmega328p is not "very compatible" with an ATmega328pb, even though they're from the SAME manufacturer. But IMNSHO, that's because someone at the company was an idiot.)