How does one work on a new git branch that depends on another git branch that is not yet merged?

Create your topic branch off of the first branch. As soon as the first is merged into master you can rebase on top of that, and assuming not too much was changed it shouldn't be a problem.

If the commits of the first branch aren't changed your new branch will stack neatly on top of that, and if the commits are changed (squashed, edited or whatever) you can always do an interactive rebase of the second branch and edit it to look good once the first branch has been merged.

Yes, I think you're on the right track. What I would do is create a new my_feature branch, perhaps work a little bit. When I realise that my_feature depends on problem_fixes, merge that branch in. This could happen right away if you know that you'll need it. Then, when my_feature is merged into master, you'll already have the changes you need.

Note that as long as you have a robust code review procedure, then if you try to merge my_feature into master before problem_fixes, then you will notice at that time.