Firstly, your maths is appalling. Let's fix that:
So in the 8-bit scenario, if you have 4 chunks, you have 255 * 4 = 1020 possible combinations, in 32 bits.
You want to count every combination of four bytes, which is 2554 = roughly four billion combinations, which is strikingly close to 232, which is what you'd expect. In fact, 232 - 2554 = 66,716,671, so you've spent sixty-six million possible combinations to reserve one magic value in each of the four bytes.
In the 2-bit scenario, to get to [the same number of] combinations, you need
We're actually looking for log3 2554, which is just over 20.
The question is, how do you determine what is the best representation of your data?
Well, firstly we decide whether we need a null terminator at all. If we know the whole range of a number will fit in a fixed-width integer type, we can just use that. It's faster and simpler to process, and often absolutely fine.
Secondly, remember we can often just use external compression. Instead of having one complex module with difficult-to-decode variable-length data, you use two simpler modules - one that acts on simple data, and one that (de)-compresses arbitrary streams or blocks of data. This may give better compression than trying to micro-optimize the storage of each field, and be less effort.
If you must use variable-length data, and you really have no way of guessing whether each field will be one byte or one terabyte, then yes, it's difficult to come up with a single solution which is optimal in all cases. But realistically this is almost unheard of.