It's actually hard to go out of your way and call malloc directly, because FFI calls are unsafe. It's a lot easier to use Box/Vec/String/etc., all of which are defined in liballoc and use the pluggable allocator interface.
I know this because I've successfully used #![no_std] libraries in places where libc doesn't exist and no function named malloc exists, and they do work. If you're having a linker issue it's almost certainly because you haven't changed the default allocator - if you have an example of this I'd be happy to take a look at debugging it.