This is simple if you use Icicles.
You can use Icicles search to search contexts of any kind, including lines. For searching lines the command is
icicle-occur, bound to
During Icicles search you type text (it can be a regexp, substring, etc.) as a search pattern to match, and the contexts that match that pattern are retained as candidates to visit/show. In other words, your search is narrowed to contexts (e.g. lines) that match what you type. And this is dynamic: change the text in the minibuffer to another pattern, and the matching contexts change immediately.
During Icicles search (and during completion more generally), you can use
C-~ anytime to narrow subtract the current matching contexts from the previous set of contexts (e.g. the original domain of contexts, such as all lines in the buffer). That is,
C-~ complements the current set of matches. Which is what you asked for.
Peripherally related to your question, you can also use
C-M-~ (same key, but with Meta- added) to complement, not the current search candidates, but the domain of contexts used from then on. This is useless if the contexts (areas to be searched) are all of the lines in the buffer, but it is quite useful for contexts that are not contiguous.
For example, there are Icicles search commands to search various THINGs (e.g., different types of sexps) as contexts, and these are not necessarily contiguous. When you hit
C-M-~ during search, instead of searching the contexts you define, Icicles searches the non-contexts. That is,
C-M-~ changes to searching the complement of the set of contexts.