You wouldn't be implementing anything in software. The hardware would have decoding built in, so it's really just a question of choosing a bluetooth audio soc with the codecs you want and paying the licensing fees.
I didn't know that codec handling was done at the hardware level. Interesting.
So the underlying idea of my post ("you can't just add new codecs in software") is ultimately correct, but for reasons completely unrelated to what I mentioned. That is, I'm wrong, but sort of stumbled into the right answer. Doubly interesting.
Now I have a ton of questions about how bluetooth audio is produced on the phone side, so that headphones only have to decode one (or a few) codec on the other side.