Eseguire azione finché una key esiste

Salve,

dovrei controllare se una key esiste (diciamo che si "autoincrementa") ed eseguire un' azione se non esiste.

Per capirci, ho un array così:

$a = array('Key1' => 'Val', 'Key2' => 'Val', 'Nonso' => 'Boh', 'Altrakey' => 'Altroboh'); 

Devo aggiungere un nuovo elemento Key => value e il nome della key dovra essere "KeyNUMERO", quindi devo controllare con un ciclo (suppongo while, ma non so come strutturarlo dato che dovrei incrementare il NUMERO) che KeyNUMERO non esista e se esiste incrementare NUMERO per ricontrollare.. La funzione è sicuramente array_key_exists, però come dicevo come strutturo il while?

Nell' esempio di $a, dovrebbe venir fuori "Key3"