Why Javascript Can't Do This -
If you make requests cross-domain (not from on your site domain) then the requests will fail. This due to a security policy called the "Same-Origin Policy" which is enforced in mainstream browsers to prevent XSS (cross site scripting). A table listed in the Same-Origin Policy Wikipedia page gives a good description of what is considered cross-domain and what is not.

To summarize, client side scripts cannot and should not be able to access sites deemed as cross-domain by the Same-Origin policy.
This means that Javascript will not be able to do what you're asking because it cannot determine anything about the links your users provide unless those links are to your own site.
This seems to work fine in IOS, but not in Android.
While this shouldn't be possible on any device, your current method most likely works because a page that doesn't exist will likely cause the device's browser to linger while it tries to load the non-existent page. While it is still lingering, your code in the timeout runs and redirects. While this is clever, it relies on several assumptions:
- The browser will linger when encountering the non-existent page.
- The browser will linger for more than 25 milliseconds.
So what's wrong with these assumptions?
You can't assume all browsers will linger. This may explain why Android devices don't seem to work for you. If the server responsible for the link being called is configured to return a 404 page then the page will load normally leaving your script unaware that the link didn't actually exist. For instance, this page doesn't exist, but a 404 page is still returned.
The length of time that a page takes to load also relies on several things such as the connection speed, the browser, the timeout/tolerance the page gives to requests that don't reply, etc. It is likely that clients using your site on a slow connection will be unable to access any sites due to it taking longer than 25 milliseconds to load them while users using a fast connection and a particular browser may experience all pages loading faster than 25 milliseconds thus thwarting your system's intent.
What Can Do This?
The proper solution to this problem requires something to be performed server side. Server side langues can access cross-domain links and determine if the page exists. Stackoverflow user karim79 shows how this can be done with the following PHP snippet (How can I check if a URL exists via PHP?):
$file = 'http://www.domain.com/somefile.jpg';
$file_headers = @get_headers($file);
if($file_headers[0] == 'HTTP/1.1 404 Not Found') {
$exists = false;
}
else {
$exists = true;
}
A call from your Javascript with ajax could then be used to send a parameter to the script and then get a response. Obviously minor tweaks would have to be made to the PHP script above to include the parameter and return value.
Lucky for you, Yahoo provides an API driven by YQL, a service they describe as:
Query, filter, and join data across Web services through one simple
language. Eliminate the need to learn how to call different APIs.
Another user looking for a similar solution (Can jQuery/js help me determine if an URL exists) got an answer from Stackoverflow user Sheikh Heera which provided the following solution utilizing the Yahoo API:
function isUrlExists(url)
{
$.getJSON("http://query.yahooapis.com/v1/public/yql?"+
"q=select%20*%20from%20html%20where%20url%3D%22"+
encodeURIComponent(url)+"%22&format=json'&callback=?", function(data){
if(data.results[0]){
alert('Exists');
}
else{
alert('Doesn\'t exist');
}
}
);
}
isUrlExists('http://google.com');
Basically Yahoo will make the request server side and allow you to get the results without you having to write anything server side yourself. This is awesome! This particular example utilizes jQuery, however, it could be done in just plain Javascript.
I've written up a JS-Fiddle with this particular method that seems to work. Check it out:
http://jsfiddle.net/L84RV/embedded/result/