Pushdown automaton with binary stack
You're on a good path!  Keep at it.  Remember that a pushdown can have a finite-state control, and you can remember up to a finite amount of information in the finite-state control.  Also, it can have $\epsilon$-transitions (so the read head doesn't consume any of the input).  Those might be helpful.