Fine-tuning a CNN for recognizing two classes, but also being able to tell if none of them is present in an image
Actually you are in the right path but in the question you are wrong in the second paragraph. 

What you should do is as follows:


change the output layer to 4 classes, dogs, cats, dogs and cats, none.
If you have so many data, don't freeze the convolutional layers and train them all but if not, freeze them and fine tune the last layers, maybe just the dense layers.