How can a site programmatically detect if cron has not run in a long time?
What is a safe and performant way for the site to periodically check
  if the 'cron_last' variable is too old, that doesn't rely on cron?


As said before by @Clive, you a script running periodically to do this check for you. Having said so, the simplest way is to create a basic module that checks the last time Drupal Cron ran succesfuly and acts based on that. You could include a drush command so you can call it via a server cronjob. E.g.


Check if cron hasn't run in X minutes and send e-mail if so, using  Drush

1) Create a file named cronwatch.drush.inc

2) Create the drush command that you will invoke via a crontab / automated task in your server. For instance, you would be running drush cronwatch every X minutes.

/**
 * Implements hook_drush_command().
 */
function cronwatch_drush_command() {
  $items = array();
  $items['cronwatch'] = array(
    'description' =&gt; dt('Check last time Drupal cron ran and send an email if necessary.'),
  );
  return $items;
}


3) Add a function to check if Drupal Cron hasn't run in longer than X minutes, send an alert email.

/**
 * Callback function for drush cronwatch command.
 */
function drush_cronwatch() {
  // Minutes since the last time cron run.
  $last_cron = variable_get('cron_last', 0);
  $minutes_ago = (time() - $last_cron) / 60;

  // How many minutes to allow without having run the cron.
  // This number should be larger than the frecuency of Drupal cron. E.g. If
  // Drupal cron is set to run every 60m, this number could be 70.
  $tolerance = 70;

  // If the cron last ran longer than tolerance minutes ago, it means that it
  // probably failed.
  if ($minutes_ago &gt;= $tolerance) {
    $to = 'you@example.com';  // E-mail to get the alerts
    $message = t('Drupal cron could not run successfuly. Last succesful run was !minutes minutes ago.', array('!minutes' =&gt; floor($minutes_ago)));
    drush_mail_send_email($to, 'Drupal Cron failed', $message);
  }
}


4) Finally, this is the function to send an e-mail via drush:    

/**
 * Send an e-mail to a specified e-mail address from within Drush.
 * @see http://drupal.org/files/mail.drush_.inc__0.txt
 */
function drush_mail_send_email($to, $subject = '', $body = '') {
  // Define $from and headers
  if (!$from = drush_get_option('from')) {
    // E-mail to send the alerts from. Replace here if desired.
    $from = ini_get('sendmail_from');
  }
  $headers = array();
  $headers['From'] = $headers['Sender'] = $headers['Return-Path'] = $headers['Errors-To'] = $from;

  // D7 implementation of drupal_mail
  if (function_exists('drupal_mail_system')) {
    // Prepare the message.
    $message = drupal_mail('drush', 'key', $to, NULL, array(), $from, FALSE);

    $message['subject'] = $subject;
    $message['body'] = array();
    $message['body'][] = $body;
    $message['headers'] = $headers;

    // Retrieve the responsible implementation for this message.
    $system = drupal_mail_system('drush', 'key');
    // Format the message body.
    $message = $system-&gt;format($message);
    // Send e-mail.
    $message['result'] = $system-&gt;mail($message);
    $result = $message['result'];

    // D6 implementation of drupal_mail_send
  }
  else {
    $message = array(
      'to' =&gt; $to,
      'subject' =&gt; $subject,
      'body' =&gt; $body,
      'headers' =&gt; $headers,
    );
    $result = drupal_mail_send($message);
  }

  // Return result.
  if ($result) {
    drush_log(dt('E-mail message sent to !to', array('!to' =&gt; $to)), 'ok');
  }
  else {
    drush_set_error('DRUSH_MAIL_ERROR', dt('An error occurred while sending the e-mail message.'));
    watchdog('cronwatch', 'An error occurred while sending the e-mail message with Drush.', array(), WATCHDOG_ERROR);
  }
}


And there you go. If Drupal Cron is set to run -let's say- every 60 min, and for some reason failed, the next time this script is executed, it will send you an alert e-mail and you can act based on that. 

---- EDIT: Added code to check without depending on Drush / Server Cronjobs ----

Check if cron hasn't run in X minutes and send e-mail if so (no Drush / Server cronjobs)

You could also run the checks without Drush nor server cronjobs. For this, you will necessarily need to hook your checks to a certain event in your website (e.g. every page load). 

In your cronwatch.module file:

1) In this case, we check on every page load, that is almost guaranteed to run periodically. However, you can use any other hook to trigger your checks.

Let's find out when the Drupal cron check was last executed.

/**
 * Implements hook_page_alter().
 *
 * Finds out when was the last time Drupal cron check was executed. If it's
 * been longer than the desired frequency, proceeds with a new check.
 *
 * We depend on page loads in order to emulate a 'periodically running' event,
 * as an alternative to a server cronjob / scheduled task.
 */
function cronwatch_page_alter() {
  // Defines how often we want to run the checks (in minutes).
  // We need this flag variable, since we don't want to make a check on
  // every single page load.
  $frequency = 60;

  // Only proceed if it's been longer than 60 minutes since the last check.
  $last_check = variable_get('cronwatch_last_check_timestamp', 0);
  $minutes_ago = (REQUEST_TIME - $last_check) / 60;

  if ($minutes_ago &lt; $frequency) {
    return;
  }

  // More than 60 min have passed since the last check. So, let's proceed with
  // a new check.
  if (cronwatch_check()) {
    // Check was succesful. Now update the 'last check timestamp' variable so
    // the next check runs an hour from now.
    variable_set('cronwatch_last_check_timestamp', REQUEST_TIME);
  }
}


2) Make the actual check for the last time Drupal cron ran. If more than X minutes have passed, send an email.

/**
 * Checks the last time Drupal cron ran, and acts based on that.
 */
function cronwatch_check() {
  // Minutes since the last time cron run.
  $last_cron = variable_get('cron_last', 0);
  $minutes_ago = (time() - $last_cron) / 60;

  // How many minutes to allow without having run the cron.
  // This number should be larger than the frecuency of Drupal cron. E.g. If
  // Drupal cron is set to run every 60m, this number could be 70.
  $tolerance = 70;

  // If the cron last ran longer than tolerance minutes ago, it means that it
  // probably failed.
  if ($minutes_ago &gt;= $tolerance) {
    $to = 'you@example.com';  // E-mail to get the alerts
    $message = t('Drupal cron could not run successfuly. Last succesful run was !minutes minutes ago.', array('!minutes' =&gt; floor($minutes_ago)));
    $mail_sent = cronwatch_mail_send_email($to, t('Drupal Cron failed'), $message);

    if ($mail_sent) {
      return TRUE;
    }
  }
  return FALSE;
}


3) Function to send an e-mail

/**
 * Sends an e-mail from the cronwatch module.
 */
function cronwatch_mail_send_email($to, $subject, $body) {
  // Let's get the mail ready to be sent.
  $module = 'cronwatch';
  $key = 'alert_mail';
  $from = variable_get('site_mail', ini_get('sendmail_from'));
  $language = language_default();

  // Build the mail, but don't send it yet.
  $message = drupal_mail($module, $key, $to, $language, array(), $from, FALSE);

  // Prepare the message.
  $message['subject'] = $subject;
  $message['body'][] = $body;

  // Retrieve the responsible implementation for this message.
  $system = drupal_mail_system($module, $key);

  // Format the message body.
  $message = $system-&gt;format($message);

  // Send e-mail (Drupal will log any error).
  $message['result'] = $system-&gt;mail($message);

  return $message['result'];
}


Only drawback is you depend on page loads, so accuracy would be affected by a website with very few or no visits (in that case, do you even need this?). And, of course, this code could be refactored, but this should do the trick.