On the MHD side, it may depend on connection volume and your hardware. You could use the 'thread per connection' mode, which would allow the thread to wait for a response without blocking other connections. Alternatively, you could use MHD's 'suspend/resume' functionality to reduce the number of MHD threads (and thus free up the primary MHD thread to service other connections/requests).
If you don't use the 'thread per connection' mode, I strongly suspect you're going to want/need to use at least 1 other thread to service the binary protocol side of things. I'm not certain, but I don't think MHD has a mechanism where you can 'service it repeatedly' from a main loop (as is common in some embedded systems or real-time applications). If your hardware can support it, I'd really recommend adding one or more threads to handle the back-end. (C++ might make that easier than straight C, by the way.)
For application structure, there are lots of ways to do it. That really doesn't have much to do with MHD. Off the top of my head, I'd consider using condition variables, wait/notify, and some kind of 'result pointer' to transfer data between threads. I do this all the time (in C++ on Linux - not sure how hard that would be to do in C or other platforms). You could also just use 2 blocking queues and have a thread on each side to process the data from one queue and feed stuff to the other queue for the other side to handle. It really depends on how many simultaneous requests you want to process.
If traffic/request volume is sufficiently low, the simplest thing to do is use MHD's 'thread per connection' mode and just do the back-end I/O in that thread. Send the request, wait for the response, and send the result back out MHD to the caller. Just make sure the back-end is thread-safe and/or the MHD side waits for a request to finish before sending another (even if it's simply by using a mutex). It's hard to know what to suggest without a lot more info.
In short - this sounds a lot more like a threading problem than any problem you might have with MHD.
Hope that helps.
Ken