The simple answer is yes - you need enough blocks of flash to support bootloader and A/B code images if you want high reliability. Before activating the new image, you can write the whole thing, verify it and potentially retry.
However this is an expensive/reliable strategy and there are things you can do to reduce the overhead. Low level support for OTA updates may also come as part of the device firmware or OS, so you can avoid rolling-your-own unless you want to learn. This feature might be described as
Partitioning your code base allows for incremental updates, best case the bootloader is able to bring up the network connection, download and verify code without needing any fall-back user code. With a local gateway, management of this task can be delegated from the low-cost endpoints.
Many devices have a small amount of word-erase flash, and even failing this you can usually set bits without needing to erase a whole block. These features can be used to manipulate jump tables and stitch together code which is updated in block sizes chunks. Even if you initially planned for a full A/B code space, you might need to fall back to a more complex scheme when the codebase grows too much.
To clarify the functionality which can be achieved with a sophisticated firmware-over-the-air solution, the bootloader and potentially a primary communication stack can remain resident whilst the full remaining user application space is re-flashed. This doesn't need any overhead (particularly if the block partitioning is soft). In the scenario where the communication stack needs to be upgraded, the region generally used for application code can be temporarily used during download and verification. Achieving this requires some support in the SoC, but 2nd and 3rd generation devices designed with this in mind do exist already.