Perhaps malloc() could allocate 1 byte extra at the start of the allocated block with some magic number written to it and free() could assert that the number is correct and change the number to mark the block as freed.
All memory allocations are now misaligned, decreasing performance. On some platforms misaligned access causes a bus error exception.
The marker would generally need to be at least 8 bytes. This would alleviate the problems, but also cause pretty significant overhead.