I was having a similar problem, the 404 page was just showing my latest post. With the title saying ‘Nothing Found For‘ followed by what ever had been entered in the url.
After a site wide search for ‘Nothing Found For‘ I found the text in the AIOSEO plugin. I deleted whatever had been set in the ‘404 Title Format:‘ setting for the plugin and my 404 is working now.
