How can I alter the HTML output of the default 403 and 404 error messages without hacking core?
Implement a custom module providing the 403/404 markup as a page callback. Note that access can be granted to anybody by setting the access callback in the menu router items to TRUE.

After enabling the custom module, you simply set the error pages in Configuration » System » Site information to the paths you defined in your hook_menu implementation.

/**
 * Implements hook_menu().
 */
function acme_menu() {
  $items['acme_404'] = array(
    'page callback' =&gt; 'acme_404',
    'access callback' =&gt; TRUE,
    'type' =&gt; MENU_CALLBACK,
  );
  $items['acme_403'] = array(
    'page callback' =&gt; 'acme_403',
    'access callback' =&gt; TRUE,
    'type' =&gt; MENU_CALLBACK,
  );
  return $items;
}

/**
 * Page callback for custom page not found.
 */
function acme_404() {
  return filter_xss(variable_get('acme_404_markup', 'custom 404 markup'));
}

/**
 * Page callback for custom access denied page.
 */
function acme_403() {
  return filter_xss(variable_get('acme_403_markup', 'custom 403 markup'));
}