Parece que ha vuelto a cambiar las cosas, y ya no es posible instalar MySQL en un servidor Debian simplemente añadiendo los repositorios non-free.
Ahora, nos tenemos que descargar un ficherito desde la propia web de MySQL, un instalador. Se recomienda ejecutar previamente un apt get update y upgrade. Vamos a ello. Lo primero, descargamos con wget:

Es posible que os pida el paquete gnup. Lo mejor que podéis hacer después de bajar el apt-config es volver a hacer un update y un upgrade. En mi caso, tuve que hacer un apt-get install gnup, y ya me fue posible instalarlo.
Además, enfrenté el siguiente problema:

No me detectaba la versión correctamente de Debian. En mi caso, estoy usando Debian 10 “Buster”, sobrenombre que se le dio a la versión. Tendréis que buscar la vuestra, si no estáis usando (que lo dudo) la 10.
Escogemos la versión que queremos, en mi caso la Server:

Después debemos elegir la versión que descargaremos, la 5 es muy usada aún en entornos de producción, pero si no quieres esa en específico, te recomiendo la 8:

Para después configurarla (en mi caso quiero un servidor de BBDD, elijo servidor):

Listo, ahora tenemos que configurar la instalación de MySQL, para añadir usuario y contraseña:

Ahora hacemos un update, para recargar los paquetes e instalamos MySQL:

Importante, debemos guardar la contraseña Root, sin ella no podremos acceder al servidor:

!Listo!, ya tenemos nuestro servidor, probamos a conectarnos:
