ALTER TABLE Client CHANGE idClient
idClient INT AUTO_INCREMENT PRIMARY KEY;
Então, quando você inserir na tabela, exclua a coluna de chave primária de incremento automático da sua inserção:
INSERT INTO Client (name, address, country)
VALUES ('name', 'address', 'country')...;
O novo valor de idClient será gerado.
Essa é a única maneira de fazer isso com segurança se houver várias instâncias de um aplicativo inserindo linhas ao mesmo tempo. Usar o método MAX(idClient) que você descreve não funcionará, porque está sujeito a condições de corrida.
