Answer: $3001$.

Since each number in the sequence, starting from the second, is greater than the previous one by at least $1$, the $9 \cdot 1000^{1000}$-th number is at least $9 \cdot 1000^{1000}$, so it has at least $3001$ digits. Denote the $n$-th number of the sequence by $a_n$, and let $k$ be the smallest index such that $a_k$ has $3002$ digits. If we show that $k > 9 \cdot 1000^{1000}$, then the $9 \cdot 1000^{1000}$-th number has at most $3001$ digits, i.e., exactly $3001$ digits.

Consider numbers from $0$ to $10^{3001} - 1$ that do not have any $1$s in their decimal representation. Padding each on the left with zeros to $3001$ digits, we get all sequences of length $3001$ consisting of digits other than $1$. There are $9^{3001}$ such sequences. Thus, among the numbers $a_1, \dots, a_{k-1}$, there are at most $9^{3001}$ numbers without a $1$ in their decimal representation (since all are at most $10^{3001} - 1$).

Now consider the process of obtaining $a_k$ from $a_1$. At each of the $k-1$ steps, we add a number from $1$ to $9$, and the number of steps where we add something other than $1$ does not exceed $9^{3001}$. Therefore,
$$10^{3001} - 1 \leq a_k - a_1 \leq 9 \cdot 9^{3001} + 1 \cdot (k-1 - 9^{3001}) = k-1 + 8 \cdot 9^{3001},$$
from which
$$k \geq 10^{3001} - 8 \cdot 9^{3001}.$$
It remains to show that $10^{3001} - 8 \cdot 9^{3001} > 9 \cdot 10^{3000}$. For this, it suffices to prove that $9^{3002} < 10^{3000}$. Note that $9^7 = 4782969 < 5 \cdot 10^6$, so $9^{28} < 5^4 \cdot 10^{24} < 10^{27}$ and $9^5 < 10^{54}$. Therefore,
$$9^{3002} = 9^5 \cdot 9^{2946} < 10^{54} \cdot 10^{2946} = 10^{3000}.$$