I figured this out.
The problem is you need to compile with both the correct C++ toolchain and the correct C++ standard library.
You were on the right track to build with the bundled clang, but you also need to compile against the bundled LibCxx (libc++). By default the bundled clang will build against libstdc++ - and that is what is causing the linking problems (ie protobuf is compiled against a different standard library to the one UnrealBuildTool is compiling the rest of the project against - so there are symbol mismatches when linking.)
Here is the full cmake command line I have found to build protobuf for unreal:
(I got the options from LinuxToolChain.cs in UnrealBuildTool.)
(You’ll need to adjust for your unreal source paths of course)
And there is a checkin of the binary result libprotobuf.a in our public Tasmania plugin:
I have tested this as linking against monolithic targets. More work needs to be done - but at least the linking problem is fixed.