I dont think there is a generic solution to this problem. The reason are
1) the headphone quality may be bad, there may be internal coupling between the mic and headphones as the wires are very close in headphones
2) The echo canceler in android is not mandatory to be implemented by all devices. Try querying it first and settings. also the echo canceler implementation may vary from device to device
3) the latency affect the performance of the echo canceler a lot as the algorithm has to adapt to the delay and buffer that much audio.
4) lower versions of android have horrible delay problems acknowledged by google itself. You may want to move to higher android version as these things have been improved greatly.
In general any API that has some direct hardware access like mic and camera , the performance varies from device to device and performance cannot be guaranteed.
you may want to look at openSLES for better audio performance and easier integration to AEC library if you are thinking of integrating.
Please look at - https://source.android.com/devices/latency_design.html Low-latency audio playback on Android https://www.youtube.com/watch?v=d3kfEeMZ65c
Hope this helps,
Regards, Shrish