A sequence $a_i$ ($i=1,\ldots$) is lexicographically smaller than sequence $b_i$ if either $a_1 < b_1$, or $a_j = b_j$ for $j=1,\ldots, k$ and $a_{k+1} < b_{k+1}$.
If I asked for the lexicographically smallest sequence of natural numbers not in the OEIS, then I think it would start $1,1,1,1,1,1,1,1,1,1,1,2$—eleven $1$'s followed by a $2$—because A055642 starts with ten $1$'s followed by a $2$.
But what about integer sequences? After seeing @RossMillikan's answer, what I should ask for is the largest of all those sequences smaller than any sequence in the OEIS.
Of course once identified, it could be added to the OEIS.
Given that you ask for naturals which do not include $0$, the first sequence lexicographically is OEIS A000012, which is all $1$'s. There is no sequence which is the next one lexicographically after this. You suggest starting with eleven $1$'s and a $2$, but then I suggest starting with twelve $1$'s and a $2$, then someone else will suggest a hundred $1$'s and a $2$, and so on.
The same problem occurs for integer sequences. Given any sequence that is missing, there is a lexicographically earlier one missing.