Or you can combine your two ideas:

> in free(), perform a trylock of the mutex
> if the trylock fails, then create a new Finalizer to postpone the
freeing of the same block to a later time,...
> ... perform the freeing of pending blocks synchronously
> when malloc() is called

If free() is called indirectly from malloc() (by the garbage collector), free() adds the block to free in a "pending free" list. Pseudo code:

-----------------------
def __init__(self):
  ...
  self._pending_free = queue.Queue()

def _exec_pending_free(self):
  while True:
    try:
      block = self._pending_free.get_nowait()
    except queue.Empty:
      break
    self._free(block)

def free(self, block):
  if self._lock.acquire(False):
     self._exec_pending_free()
     self._free(block)
  else:
     # malloc holds the lock
     self._pending_free.append(block)

def malloc():
  with self._lock:
    self._malloc()
    self._exec_pending_free()
-----------------------

Problem: if self._pending_free.append() appends whereas malloc() already exited, the free will have to wait until the next call to malloc() or free(). I don't know if this case (free() called while malloc() is running, but malloc() exits before free()) really occur: this issue is a deadlock because free() is "called" from malloc(), and so malloc() waits until the free() is done. It might occur if the garbage collector calls free after _exec_pending_free() but before releasing the lock.