Toasty GrapheneOS currently does not have and does not plan to add the call recording feature. And as far as I know there are no open source way to do it without rooting (which according to my knowledge breaks the GOS's security model).
Absolutely there is a way to do this without "rooting". NONE of the call recording applications that are available actually use root! The mistake you are making is in understanding the nature of the elevated privileges required and how that relates to Magisk.
The reality is that how programs are installed determines what kind of privileges they have access to. If an application is installed as a privileged system application (which means that the APK is installed in /system/priv-app/), then it gains access to an additional set of privileges that a regular user-installed application won't have access to, and THESE privileges are sufficient to enable call recording.
Magisk has a way of placing an application in the privileged location without actually modifying the filesystem. THAT is what is being used to make call recording work. It does NOT grant root privileges to the call recording application!
So if you want to make call recording work on GrapheneOS without Magisk, you need only place the application in the privileged location DURING SYSTEM BUILD.
BCR is a very concise and open source call recording application that could easily be audited for safety and included. GrapheneOS has come up with a huge heaping pile of excuses against including it, such as "the GPLv3 license is not compatible with GrapheneOS" -- which is totally nonsense since GrapheneOS has a TON of GPL components already! The kernel itself is GPLv2, which is close. There are also a bunch of GPLv2 and GPLv3 components in /external/