If you don't care about the order of the strings, just keep track of the number of strings and replace the address of the deleted string with the address of the last string. Then decrease the count by one. If order is important than use a linked list as suggested by rproffitt. It's a little more work but making a library of linked list functions is worth the trouble for what you will learn by doing it.
Seems like the answer to this question is "It depends", as it is with lots of questions. Linked list versus array? It depends. Move thousands of bytes of memory versus a new array and a big deep copy versus some clever pointer manipulation versus... It depends. On a lot of stuff. More info needed as far as what the scarce resources are, how often deletions happen, etc., etc.
I have to agree with rproffitt on the last point though. I imagine I could come up with a scenario where setting more than one byte to 0 to signify an empty string made sense, but unless there is a very good reason to do so, I don't see the need. The entire point of C strings is that once you hit that NULL terminator, you don't care what may be beyond it.