Echo cancellation supporting long delays and without frequency domain processing AEC algorithms mostly rely on LMS adaptive filtering, i.e. you update FIR filter coefficients then perform the filtering. Theoretically, the FIR must be as long as the maximum echo length you want to cancel. For instance to cancel delays up to 500ms on a 48kHz signal, you'll need a 24000 point FIR.
When your memory and processing power limitations make it so you can neither afford to perform 24000 MACs per processed sample, nor to use FFT-based fast convolution algorithms, is there a way around for cancelling such potentially high length echoes in a more affordable way, given delay is unknown and potentially variable?

I was wondering maybe about some other algorithm running in parallel that could assess the approximate delay, then use an adaptive length delay line + a shorter adaptive FIR filter (up to a few hundreds taps is OK)

Does this make sense? Any other neat approach to suggest?
I believe you logic is reasonable. The fact that there are companies offering algorithms for long echo tail (even above 1 second) with reasonable performance indicates that an algorithm similar to your suggested logic can work.