Tras seleccionar los datos en cuestión, comencé a buscar en las opciones de Ordenar y no existe ninguna opción incluida en Excel para ordenar de esta forma aleatoria.

¿Cómo podemos hacerlo entonces?
La solución es muy fácil: Simplemente tenemos que añadir una columna adicional a nuestros datos y completar todas las celdas de dicha columna con la fórmula:
=ALEATORIO()
De esta forma todas las celdas de esa columna se completarán aleatoriamente con valores entre 0 y 1, por lo que podremos ordenar por dicha columna y tendremos nuestros datos originales totalmente ordenados de forma aleatoria.
Aviso: Una vez que pulsemos ordenar sobre la columna de números aleatorios veremos como dicha columna vuelve a aparecer desordenada. Eso sucede porque los números aleatorios vuelven a recalcularse, aunque el resultado de dicha columna es indiferente, pudiendo eliminarla al tener el resto de datos ordenados aleatoriamente como era nuestra intención.