Auto Increment a column that is not unique...?
That seems possible in MyISAM but afaik not using InnoDB:

CREATE TABLE `invoice_sequences` (
  `company_id` int(11) NOT NULL,
  `invoice_id` int(11) NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`company_id`,`invoice_id`)
) ENGINE=MyISAM;


http://sqlfiddle.com/#!9/d135c/1 (if the fiddle returns an error, try again; it seems a bit slow sometimes).