Our application has an area where users are able to change background colours, text colours and other things.
I'm wondering that as we are trying to make our application AA compliant, would this feature have to be removed? As we don't have much control on what colours they pick and the contrast that they would choose.
As long as your default background and foreground colors for visitors satisfies 1.4.3 Contrast minimum then it's ok.
The technique you are using is an approach of one the suggested techniques for this point: G156: Using a technology that has commonly-available user agents that can change the foreground and background of blocks of text