Assuming 256-bit hash output, how does the (average) number of nonces I need to try (to solve the proof-of-work puzzle) grow with the number of leading zeroes required, n? Is there a bound on this number?
If you want n zeroes when written in binary, 2n.
If you want n zeroes when written in decimal, 10n
If you want n zeroes when written in hexadecimal, 16n.
If you want n zero bytes, 256n.
However, none of these things are relevant in terms of Bitcoin. The difficulty is not the number of zeroes required; the difficulty is the minimum ratio between a well-defined maximum value, and the hash you got (when interpreted as a 256-bit unsigned integer).
In practice, the formula is that you need difficulty * 248 / 65535 attempts.
I think that you need on average difficulty * 232 trials to solve the proof-of-work puzzle. Cf the bitcoin specification.