Create a shallow logic circuit that increments a binary number
You are on the right track with a parallel-prefix circuit.  You already have the key when you said


  The carry has to ripple through the first sequence of consecutive bits set to 1.


Now suppose you are figuring out the output for, say, the 5th bit.  What function of the first 4 bits tells you whether the 5th bit should ripple?  That's the function you need to make a parallel-prefix circuit for.