Te explicas perfectamente. Lo que pasa es que no entiendo por que no te está funcionando. Con la instrucción:
Código SQL
[-]
alter table tabla auto_increment=5000
los subsecuentes registros deberían ser 5000, 5001, 5002, etc. Así lo acabo de probar. Lo que sí es que no estoy seguro de que un campo autoincremental realmente te sirva ya que en cuestión de facturas muchas veces es requisito que no haya "hoyos" en la numeración y con transacciones, cuando cancelas una, el autoincremental que le correspondía queda sin usar.
// Saludos