Use una tabla de secuencia y un disparador, algo como esto:
drop table if exists users_seq;
create table users_seq
(
next_seq_id int unsigned not null default 0
)engine = innodb;
drop table if exists users;
create table users
(
user_id int unsigned not null primary key,
username varchar(32) not null
)engine = innodb;
insert into users_seq values (0);
delimiter #
create trigger users_before_ins_trig before insert on users
for each row
begin
declare id int unsigned default 0;
select next_seq_id + 1 into id from users_seq;
set new.user_id = id;
update users_seq set next_seq_id = id;
end#
delimiter ;
insert into users (username) values ('f00'),('bar'),('bish'),('bash'),('bosh');
select * from users;
select * from users_seq;
insert into users (username) values ('newbie');
select * from users;
select * from users_seq;