$ch = curl_init("http://www.example.com/favicon.ico");
curl_setopt($ch, CURLOPT_NOBODY, true);
$retcode = curl_getinfo($ch, CURLINFO_HTTP_CODE);
// $retcode >= 400 -> not found, $retcode = 200, found.
@Lyth 3XX retcodes aren't an error, but a redirection. Those should be either handled manually or using CURLOPT_FOLLOWLOCATION.
Anyway, you only save the cost of the HTTP transfer, not the TCP connection establishment and closing. And being favicons small, you might not see much improvement.
Caching the result locally seems a good idea if it turns out to be too slow.
HEAD checks the time of the file, and returns it in the headers. You can do like browsers and get the CURLINFO_FILETIME of the icon.
In your cache you can store the URL => [ favicon, timestamp ]. You can then compare the timestamp and reload the favicon.
Some sites block access if you don't provide a user agent string, so I suggest following this guide to add CURLOPT_USERAGENT in addition to CURLOPT_NOBODY: davidwalsh.name/set-user-agent-php-curl-spoof
Use curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, false); as well to make sure same code works for URL's starting with HTTPS!
You can instruct curl to use the HTTP HEAD method via CURLOPT_NOBODY.
just a note: retcode errors on all 400 codes so the validation would be >= not just >