You cannot remove immediately the previous memory allocator because that would invalidate all memory addresses given by that memory allocation algorithm. when applications or kernel modules free all memory allocated by the previous algorithm then that is only the time wherein you can safely remove the previous one. So my current concept, which has a lot of problems, is that new malloc requests go to the new algorithm and if there is a free request, the heap interface determines who owns that free request and sends it to that algorithm.
Umm, excuse me, but what level of memory allocation are you talking about? I mean, usually there is page-allocator on the bottom. Then there's kernel malloc, then there's the virtual memory system, and then there's user level malloc or garbage collectors or whatever.
Now, let's take one at a time. Replacing the page-allocator on the fly is quite simple, just move all free pages from one allocator to another (in effect allocating all pages from the old allocator to the new one) and provide some interface for the new allocator to reuse any relevant data in case there's some. But then again, this level is usually just a stack of free pages, so what's the point.
In kernel level malloc, one will want to redirect all the allocation to the new malloc when switching. Here we have the problem that different allocators are going to use different schemes for dividing memory, so it's non-trivial to transfer allocations from one system to another. In any case, to replace such allocator, I'd probably implement some object-system, which has an interface consisting of malloc/free/realloc equivalents, and then explicitly use one implementation using a pointer. One could define the "default" allocator, switch it on the fly, or request all kernel modules/whatever to allocate memory from the other allocator and move data over. It's not fast, but that's probably the most reasonable thing to do, if one really wants to move over.
There's a problem with this though if one allows pointers between different modules, but even then one can always add a level of indirection similar to what some compacting garbage collectors do. This takes a small performance hit though. Other possibilities include to add a lot of glue to all interfaces just to communicate memory changes, or to require all allocators to handle existing allocations of any kind gracefully, and build an interface for transferring stuff over from one to another.
Now, virtual memory allocating is a similar problem, but since we are now dealing with pages, we have same size of basic unit in every allocator, so it's just a question of building an interface for transferring allocations over from one allocator to another, and then requiring all allocators to implement this interface. If performance (of allocator changes) is not issue, then this is almost trivial, and I can't imagine anyone wanting to change all the time. If virtual memory works on process level, one can even use different allocators for different processes, although this certainly adds overhead to shared memory and copy-on-write scenarios.
Finally, application-level malloc library has nothing to do with operating system kernels (as long as we have some interface to virtual memory management to request mappings for more pages).
So, which memory manager were you talking about?