Is de zin 'We konden kiezen uit allerlei soorten broodbeleg' goed?

Ja, deze zin is prima. Maar soorten kan ook worden weggelaten: 'We konden kiezen uit allerlei broodbeleg.'

Allerlei is een samenvoeging van al en lei. Dat laatste is een verouderd woord dat 'wijze, soort' betekent. Allerlei betekent dus oorspronkelijk 'van alle soorten'. Allerlei soorten broodbeleg werd vroeger dan ook als 'dubbelop' gezien, maar bijna niemand is zich er nog van bewust dat lei op zichzelf al 'soort' betekent. Het Woordenboek der Nederlandsche Taal (WNT) vermeldt in 1884 al: “Daar het begrip van soort reeds door lei wordt uitgedrukt, is de zegswijze allerlei soort (soorten) of allerlei slag eigenlijk eene tautologie. In de dagelijksche spreektaal is zij echter niet ongewoon, en men vindt ze ook bij goede schrijvers.”

Allerlei heeft nu voor bijna iedereen de betekenis 'veel'. De keuze tussen allerlei soorten broodbeleg, allerlei broodbeleg en veel soorten broodbeleg is vrij.

Andere woorden die met -lei zijn gevormd: enerlei ('van dezelfde soort'), enigerlei ('van een of andere soort', 'welke ook'), generlei ('van geen enkele soort, volstrekt geen'), meerderlei ('meer'), menigerlei ('van menige soort') en velerlei ('van/in veel soorten').