Google Apps Script to find mobile phone numbers meeting certain criteria (look inside "updateNumber()" and "fixNumbersFromGoogleContacts()" for details) and add a ninth digit to them. Scans all phone numbers in your Google Contacts, using official Google APIs. Also includes a simple and ugly UI for the most basic usage.

digit9brazil.js

// digit9brazil.gs
// Google Apps Script
//
// Objective:
//   Find mobile phone numbers meeting certain criteria (look inside "updateNumber()" and
//   "fixNumbersFromGoogleContacts()" for details) and add a ninth digit to them.
//
// Live link:
// https://script.google.com/macros/s/AKfycbzWlGLgZmA0lygkwMLp3p6RrRFIbBfVdKGXaUAcJCJo59R492E/exec
//
// Source-code:
// https://gist.github.com/denilsonsa/7165746
// https://script.google.com/d/1Jd3p0m0WS9Jjg1p8ztXDflQkCHZdj6BC36c5ZedgOov3vmRBF_4_pc_Y/edit
// http://denilson.sa.nom.br/blog/2013-10-26/bulk-editing-your-google-contact-list/
//
// References:
// http://www.anatel.gov.br/Portal/verificaDocumentos/documentoVersionado.asp?numeroPublicacao=333184&documentoPath=333184.pdf
// http://www.anatel.gov.br/Portal/exibirPortalNivelDois.do?codItemCanal=1722
// http://www.anatel.gov.br/Portal/exibirPortalNivelDois.do?codItemCanal=1794
// http://www.embratel.com.br/Embratel02/cda/portal/0,2997,PO_P_11590,00.html
// https://script.google.com/
// https://developers.google.com/apps-script/reference/contacts/
// https://developers.google.com/apps-script/reference/ui/

// Updates a single phone number, returns the updated version.
// If no update is needed, returns null.
function updateNumber(oldnum) {
  // DDDs com o nono dígito já adicionado:
  // SP: 11, 12, 13, 14, 15, 16, 17, 18, 19
  // RJ: 21, 22, 24
  // ES: 27, 28
  // PA: 91, 93, 94
  // AM: 92, 97
  // RR: 95
  // AP: 96
  // MA: 98, 99
  // - 2015-05-31 -
  // PE: 81, 87
  // AL: 82
  // PB: 83
  // RN: 84
  // CE: 85, 86
  // PI: 86, 89
  // - 2015-10-11 -
  // MG: 31, 32, 33, 34, 35, 37, 38
  // BA: 71, 73, 74, 75, 77
  // SE: 79
  // DDDs ainda sem o nono dígito:
  // - 2016-05-29 -
  // DF: 61
  // GO: 62, 64, 65
  // TO: 63
  // MT: 66
  // MS: 67
  // AC: 68
  // RO: 69
  // - 2016-11-06 -
  // PR: 41, 42, 43, 44, 45, 46
  // SC: 47, 48, 49
  // RS: 51, 53, 54, 55

  // TODO: When changing these dates, should also update them in fixNumbersFromGoogleContacts().
  var today = new Date();
  var re_ddd = /^(1[1-9]|2[12478]|3[1234578]|7[134579]|8[1-9]|9[1-9])$/;
  if (today.valueOf() >= (new Date(2016, 4, 29)).valueOf()) {
    re_ddd = /^(1[1-9]|2[12478]|3[1234578]|6[1-9]|7[134579]|8[1-9]|9[1-9])$/;
  } else if (today.valueOf() >= (new Date(2016, 10, 6)).valueOf()) {
    re_ddd = /^(1[1-9]|2[12478]|3[1234578]|4[1-9]|5[1345]|6[1-9]|7[134579]|8[1-9]|9[1-9])$/;
  }

  var match;

  // Considerando prefixos em formatos conhecidos (+55xx, 0xx, 0yyxx, 90xx, 90yyxx, xx).
  // Seguidos de 7, 8, 9 (dígito de celular).
  // Seguido de 7 dígitos (i.e. número de DD + 8 dígitos).
  var cleaned_number = oldnum.replace(/[- .()]/g, '');
  var re_format = /^(?:\+55|0|0[0-9]{2}|90|90[0-9]{2}|)([0-9]{2})[789][0-9]{7}$/;
  match = re_format.exec(cleaned_number);
  if (!match) {
    return null;
  }
  var ddd = match[1];
  
  if (!re_ddd.test(ddd)) {
    return null;
  }

  // Separando o prefixo+DDD do número.
  var re = /^\s*(.*)([789](?:[- .]*[0-9]){7}[-.]*)\s*$/;
  match = re.exec(oldnum);
  if (match) {
    var newnum = match[1] + '9' + match[2];
    return newnum;
  }
  return null;
}

// should_apply:
//   false = dry-run, shows what will be changed, but do not change anything.
//   true  = for real, apply all the changes.
function fixNumbersFromGoogleContacts(should_apply) {
  var msg = '';
  var total_phones = 0;
  var total_modified = 0;

  // TODO: When changing these dates, should also update them in updateNumber().
  var estados = 'AL, AM, AP, BA, CE, ES, MA, MG, PA, PB, PE, PI, RJ, RN, RR, SE, SP';
  var extra_msg = 'Tente novamente a partir de 29 de maio de 2016 para considerar outros estados.\n';
  var today = new Date();
  if (today.valueOf() >= (new Date(2016, 4, 29)).valueOf()) {
    estados = 'AC, AL, AM, AP, BA, CE, DF, ES, GO, MA, MG, MS, MT, PA, PB, PE, PI, RJ, RN, RO, RR, SE, SP, TO';
    extra_msg = 'Tente novamente a partir de 6 de novembro de 2016 para considerar todos estados.\n';
  } else if (today.valueOf() >= (new Date(2016, 10, 6)).valueOf()) {
    estados = 'todos os estados (AC, AL, AM, AP, BA, CE, DF, ES, GO, MA, MG, MS, MT, PA, PB, PE, PI, PR, RJ, RN, RO, RR, RS, SC, SE, SP, TO)';
    extra_msg = '';
  }  

  msg += 'Procurando por telefones de ' + estados + '.\n';
  msg += extra_msg;

  var contacts = ContactsApp.getContacts();
  for (var i = 0; i < contacts.length; i++) {
    var contact = contacts[i];
    var phones = contact.getPhones();
    total_phones += phones.length;
    for (var j = 0; j < phones.length; j++) {
      var phone = phones[j];
      var oldnum = phone.getPhoneNumber();
      var newnum = updateNumber(oldnum);
      if (newnum) {
        total_modified++;
        var msgline = (should_apply ? 'Alterando' : 'A ser alterado') + ': "' +
          oldnum + '" para "' + newnum + '" (' + contact.getFullName() + ')';
        msg += msgline + '\n';
        //Logger.log(msgline);

        if (should_apply) {
          phone.setPhoneNumber(newnum);
        }
      }
    }
  }

  if (should_apply) {
    msg += 'Concluído!\n';
  }
  msg += total_modified + ' números ' + (should_apply ? 'modificados' : 'a serem alterados') +
    ', de um total de ' + total_phones + ' telefones em ' + contacts.length + ' contatos.\n';
  //Logger.log('Terminado!');
  return msg;
}

function newPanel(app, msg) {
  var form = app.createFormPanel();

  var title = app.createLabel('Adicione o dígito 9 aos contatos da sua agenda Google');
  title.setStyleAttributes({
    fontSize: '2em',
    margin: '0 1ex'
  });
  
  var anchor = app.createAnchor('https://www.google.com/contacts/', 'https://www.google.com/contacts/');
  
  var extra_links = app.createFlowPanel();
  extra_links.add(app.createInlineLabel('Escrito por '));
  extra_links.add(app.createAnchor('Denilson Sá', 'http://about.me/denilsonsa'));
  extra_links.add(app.createInlineLabel(', código-fonte disponível no '));
  extra_links.add(app.createAnchor('Google Apps Script', 'https://script.google.com/d/1Jd3p0m0WS9Jjg1p8ztXDflQkCHZdj6BC36c5ZedgOov3vmRBF_4_pc_Y/edit'));
  extra_links.add(app.createInlineLabel(' e no '));
  extra_links.add(app.createAnchor('GitHub Gist', 'https://gist.github.com/denilsonsa/7165746'));
  extra_links.add(app.createInlineLabel('. '));
  extra_links.add(app.createAnchor('Postagem no meu blog', 'http://denilson.sa.nom.br/blog/2013-10-26/bulk-editing-your-google-contact-list/'));
  extra_links.add(app.createInlineLabel('.'));

  var radioDoNotApply = app.createRadioButton('apply', 'Mostrar possíveis mudanças, porém não modificar a lista de contatos.');
  radioDoNotApply.setFormValue('no');
  radioDoNotApply.setValue(true);
  var radioApply = app.createRadioButton('apply', 'Modificar a lista de contatos e mostrar um relatório do que foi modificado.');
  radioApply.setFormValue('apply');

  var text = app.createLabel(msg);
  text.setId('text');
  text.setStyleAttribute('white-space', 'pre-wrap');

  var button = app.createSubmitButton('OK');

  var panel = app.createVerticalPanel();
  panel.setSpacing(5);
  panel.add(title);
  panel.add(anchor);
  panel.add(extra_links);
  panel.add(radioDoNotApply);
  panel.add(radioApply);
  panel.add(button);
  panel.add(text);
  form.add(panel);

  if (app) {
    app.add(form);
  }

  return panel;
}

function getOrPost(e, app, is_post) {
  var msg = '';
  if (is_post) {
    var should_apply = e.parameter.apply === 'apply';
    msg += fixNumbersFromGoogleContacts(should_apply);
  }
  // msg += Logger.getLog();
  newPanel(app, msg);
}

function doGet(e) {
  var app = UiApp.createApplication();
  app.setTitle('Adiciona dígito 9 a celulares de RJ e ES');

  getOrPost(e, app, false);
  return app;
}

function doPost(e) {
  var app = UiApp.getActiveApplication();

  getOrPost(e, app, true);
  return app;
}

////////////////////////////////////////////////////////////
// Ad-hoc unit testing:
function assertWorks(before, expected, msg, index) {
  if (msg) {
    msg = ' (' + msg + ')';
  } else {
    msg = '';
  }
  if (index !== undefined && index !== null) {
    index = '[' + index + '] ';
  } else {
    index = '';
  }

  var actual = updateNumber(before);
  if (actual === expected) {
    return {
      success: true,
      msg: index + 'OK  : "' + before + '" -> "' + expected + '"' + msg
    };
  } else {
    return {
      success: false,
      msg: index + 'FAIL: "' + before + '" -> "' + actual + '" !== "' + expected + '"' + msg
    };
  }
}

var unitTests = [
  // Gvim Tabularize plugin:
  // :Tabularize /, /l0l1

  {before: '0800 999 9999'        , expected: null                   , msg: '0800'},
  {before: '08009999999'          , expected: null                   , msg: '0800'},
  {before: '0800 99 9999'         , expected: null                   , msg: '0800'},
  {before: '0800999999'           , expected: null                   , msg: '0800'},
  {before: '0900 999 9999'        , expected: null                   , msg: '0900'},
  {before: '09009999999'          , expected: null                   , msg: '0900'},
  {before: '0900 99 9999'         , expected: null                   , msg: '0900'},
  {before: '0900999999'           , expected: null                   , msg: '0900'},

  {before: '2345-6789'            , expected: null                   , msg: 'sem DDD'},
  {before: '23456789'             , expected: null                   , msg: 'sem DDD'},
  {before: '9876-6789'            , expected: null                   , msg: 'sem DDD'},
  {before: '98766789'             , expected: null                   , msg: 'sem DDD'},
  {before: '99876-6789'           , expected: null                   , msg: 'sem DDD'},
  {before: '998766789'            , expected: null                   , msg: 'sem DDD'},

  {before: '+55 (21) 23.45-67.89' , expected: null                   , msg: '+55 21 fixo'},
  {before: '+55 (21) 2345-6789'   , expected: null                   , msg: '+55 21 fixo'},
  {before: '+55 21 2345-6789'     , expected: null                   , msg: '+55 21 fixo'},
  {before: '+55 21 23456789'      , expected: null                   , msg: '+55 21 fixo'},
  {before: '+55 2123456789'       , expected: null                   , msg: '+55 21 fixo'},
  {before: '+552123456789'        , expected: null                   , msg: '+55 21 fixo'},

  {before: '(21) 2345-6789'       , expected: null                   , msg: '21 fixo'},
  {before: '21 2345-6789'         , expected: null                   , msg: '21 fixo'},
  {before: '2123456789'           , expected: null                   , msg: '21 fixo'},

  {before: '0 (21) 2345-6789'     , expected: null                   , msg: '021 fixo'},
  {before: '(021) 2345-6789'      , expected: null                   , msg: '021 fixo'},
  {before: '021 2345-6789'        , expected: null                   , msg: '021 fixo'},
  {before: '02123456789'          , expected: null                   , msg: '021 fixo'},

  {before: '+55 (21) 998.76-67.89', expected: null                   , msg: '+55 21 novo movel'},
  {before: '+55 (21) 99876-6789'  , expected: null                   , msg: '+55 21 novo movel'},
  {before: '+55 21 99876-6789'    , expected: null                   , msg: '+55 21 novo movel'},
  {before: '+55 21 998766789'     , expected: null                   , msg: '+55 21 novo movel'},
  {before: '+55 21998766789'      , expected: null                   , msg: '+55 21 novo movel'},
  {before: '+5521998766789'       , expected: null                   , msg: '+55 21 novo movel'},

  {before: '(21) 99876-6789'      , expected: null                   , msg: '21 novo movel'},
  {before: '21 99876-6789'        , expected: null                   , msg: '21 novo movel'},
  {before: '21998766789'          , expected: null                   , msg: '21 novo movel'},

  {before: '0 (21) 99876-6789'    , expected: null                   , msg: '021 novo movel'},
  {before: '(021) 99876-6789'     , expected: null                   , msg: '021 novo movel'},
  {before: '021 99876-6789'       , expected: null                   , msg: '021 novo movel'},
  {before: '021998766789'         , expected: null                   , msg: '021 novo movel'},

  {before: '+54 21 98766789'      , expected: null                   , msg: 'internacional de outro pais ficticio'},

  {before: '+55 (21) 98.76-67.89' , expected: '+55 (21) 998.76-67.89', msg: '+55 21 velho movel'},
  {before: '+55 (21) 9876-6789'   , expected: '+55 (21) 99876-6789'  , msg: '+55 21 velho movel'},
  {before: '+55 21 9876-6789'     , expected: '+55 21 99876-6789'    , msg: '+55 21 velho movel'},
  {before: '+55 21 98766789'      , expected: '+55 21 998766789'     , msg: '+55 21 velho movel'},
  {before: '+55 2198766789'       , expected: '+55 21998766789'      , msg: '+55 21 velho movel'},
  {before: '+552198766789'        , expected: '+5521998766789'       , msg: '+55 21 velho movel'},

  {before: '(21) 9876-6789'       , expected: '(21) 99876-6789'      , msg: '21 velho movel'},
  {before: '21 9876-6789'         , expected: '21 99876-6789'        , msg: '21 velho movel'},
  {before: '2198766789'           , expected: '21998766789'          , msg: '21 velho movel'},

  {before: '0 (21) 9876-6789'     , expected: '0 (21) 99876-6789'    , msg: '021 velho movel'},
  {before: '(021) 9876-6789'      , expected: '(021) 99876-6789'     , msg: '021 velho movel'},
  {before: '021 9876-6789'        , expected: '021 99876-6789'       , msg: '021 velho movel'},
  {before: '02198766789'          , expected: '021998766789'         , msg: '021 velho movel'},

  {before: '099 (21) 9876-6789'   , expected: '099 (21) 99876-6789'  , msg: '021 velho movel com operadora ficticia 99'},
  {before: '(09921) 9876-6789'    , expected: '(09921) 99876-6789'   , msg: '021 velho movel com operadora ficticia 99'},
  {before: '09921 9876-6789'      , expected: '09921 99876-6789'     , msg: '021 velho movel com operadora ficticia 99'},
  {before: '0992198766789'        , expected: '09921998766789'       , msg: '021 velho movel com operadora ficticia 99'},

  {before: '9099 (21) 9876-6789'  , expected: '9099 (21) 99876-6789' , msg: '021 velho movel a cobrar'},
  {before: '909921 9876-6789'     , expected: '909921 99876-6789'    , msg: '021 velho movel a cobrar'},
  {before: '90992198766789'       , expected: '909921998766789'      , msg: '021 velho movel a cobrar'},

  {before: '', expected: null, msg: 'vazio'}
];

function runTestsAndLogResults() {
  var num_successes = 0;
  for (var i = 0; i < unitTests.length; i++) {
    var u = unitTests[i];
    var r = assertWorks(u.before, u.expected, u.msg, i);
    if (r.success) {
      num_successes++;
    } else {
      Logger.log(r.msg);
    }
  }
  Logger.log(num_successes + '/' + unitTests.length + ' have succeeded');
  if (num_successes == unitTests.length) {
    Logger.log('This was a triumph! Huge success!');
  } else {
    Logger.log('You FAIL!');
  }
}

Cool! I didn't know this Google Apps' feature. Man, put this script in a Github repo, so you can accept pull requests.