I just tried it with a vanilla, freshly downloaded ndk-r8d and a small Objective-C program compiled without problems, so it looks like my hunch was correct.
Of course, it didn't link because there is no runtime, but providing one is a much smaller effort than reconfiguring the entire toolchain. After that, it gets interesting...
Update: after getting a runtime, it linked and ran on my Galaxy II test phone.