Crealo como VARCHAR y con el atributo UNIQUE KEY. La parte de generación de la clave la vas a tener que hacer con PHP.
Una forma sería usando
uniqid(), por ejemplo. Depende de vos cómo generás esa clave. Además, podés crear una función para verificar en la base de datos si no existe y generar otra.
A menos que tengas una base de datos de miles y miles de registros, creo que esto no debería darte problemas de rendimiento o algo así que sean notables.