Checking the uniqueness of a new journal's name
Consult scholar databases such as Scopus, Web of Science / Journal Citation Report, Scimago...

(This in addition to googling, of course, not instead of it.)

If it's neither on Google nor on these databases, it's effectively like it has never existed.

Another thing that you may want to check is that there is no journal with the exact same name but in another language. For instance, you don't want to end up with a journal called "Annals of Mathematics" and another one called "Mathematische Annalen"; that's just unnecessarily confusing for German speakers, right?