When do I need consent from websites owners?
Under U.S.-like laws - you need this every time. In layman's terms, by default, you can look at public site areas and only look, no duplicating or storing, etc. Despite that even your browser does it freely, laws are convoluted here. If in a special agreement published on a site or in some other explicit form is not stated a permission for this usage, you should not do it. There also may be an explicit mark about public domain or a standard open-source license. But, even this public agreement isn't enough for your purposes.
Few of the potential problems:
Use protected by legal rights data isn't legal. (may be covered by a public
agreement or a written permission)
If you interfering with sites' availability via additional load, this may be a hostile act as well. (not only an admin's ban, this is a potential legal issue)
Even if the site owner allow it, you can break some federal laws -
about personal data collection or something else, this is a question for a licensed lawyer. Also, more information needed for answer from this point of view.
So, yes, the written permission is the only legal way to dig somewhere and even this could be insufficient. People do sometimes their own similar projects without any permissions, maybe, because they think, this is too boring and slow to write some letters and do a legality research. However, you want to publish the results about work with thousands of thousands web pages. So, "cover your back" isn't a meaningless paranoidal phrase in your case. And this is only a few obvious legal concerns, also there're more ethical and technical problems with using web resources in not allowed by their owners ways.
If you just lightly ping every few seconds for checking availability of some serious sites, some of them just ban your bot after a while. Others log your activity and use the log if this will becomes a problem. I'd personally banned many harmful crawlers and filled a bunch of complains about unclear automatic requests which was loading resources dedicated for clients.