It feels like having to grab a mutex every time I want to modify some data will quickly turn my multi-threaded game engine into an effectively single-threaded one, as all other threads will be blocked.
Yep, therefor you should avoid this as much as possible. This is somewhat special about game-development, sometimes an application developer will rejoice when a process finishes after just below 200ms, whereas a game developer will break down once a process needs more then 2ms. And synchronisation is one of the fastes ways to surpass the 2ms
This works fine if there aren't many objects to draw, but if I understand this correctly, some synchronisation problems could occur if the rendering frame rate ever drops to the rate of game loop updates.
How do you balance the need for thread-safety
You dont need to balance thread-safety, because your code must be thread-safe period. It is just the matter how hard it is to ensure thread-safety. If you use mutex/semaphores/critical sections etc. it is quite easy, but potentially slow. If you use lock-less sync by contract, you are at a much higher risk of including bugs, but it is much faster.
On the other hand, maximum CPU usage is not always needed, and modern, powerful CPUs remove the burden of hobby/indie developer of squezzing out the last drop of performance. So, as long as you don't try to invent the next block-buster AAA engine, I would sugguest to use a good mix of manageable code and block-less concurrrency behavior, which feels comfortable. Just remember, the best, fastest code is worth nothing, if you can't handle it over a long period.