La tua idea è buona, ma credo di aver trovato un codice ancora più efficiente (sfogliando le API di Matcher)

Guarda:
codice:
public static String aggiungiAlt(String html) {

  Pattern pattern = Pattern.compile("(<\\s*IMG.*?)>", Pattern.CASE_INSENSITIVE);
  Matcher matcher = pattern.matcher(html);

  StringBuffer sb = new StringBuffer();
  while(matcher.find()) {
    matcher.appendReplacement(sb, matcher.group(1) + " alt=\"\">");
  }
  matcher.appendTail(sb);
  return sb.toString();

}
Praticamente scorre i vari match (tramite il metodo find() che fa da cursore) e li sostituisce con group(1) + " alt=\"\">", dove group(1) è la parte di pattern che sta tra le parentesi.

Ora funziona tutto
Grazie comunque per l'aiuto