Mysql Incremento automático int de datos similares

Como se documenta en Uso de AUTO_INCREMENT :

Por lo tanto, podrías hacer:

CREATE TABLE my_table (
  firstname VARCHAR(31) NOT NULL,
  lastname  VARCHAR(31) NOT NULL,
  counter   BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (lastname, counter)
) Engine=MyISAM;

INSERT INTO my_table
  (firstname, lastname)
VALUES
  ('james', 'smith' ),
  ('terry', 'smith' ),
  ('john' , 'smith' ),
  ('jerry', 'fields'),
  ('tom'  , 'straus')
;

Véalo en sqlfiddle .