I believe you are encountering an analogous issue to that described in Optional Computed Block handling in Plugin Framework.
The schema you have defined is using ListNestedBlock, and the block is effectively Optional. If the configuration is empty, and does not contain a value for example_block_attr, then this will be treated as a zero-length list. Mutating this value during the Create function is not allowed, as this would introduce a discrepancy between the configuration and the planned value, which gives rise to the error that you have encountered:
block count changed from 0 to 1
Effectively, your provider needs a mechanism to store additional values when the example_block_attr length is zero. I believe that the only option you have in this case is to proceed as described in Optional Computed Block handling in Plugin Framework - #4 by bendbennett