First of all, whoever dreamed up these requirements may not have known what they were demanding. This is a tall order! Scholars in these early centuries didn't record the songs of the people very often, and when they did, they almost never recorded the melodies. If they did record the melodies, they are devilish hard to interpret.
Once interpreted, they may not sound like much.

Where do you live? Do you have access to a university library (preferably one connected to a conservatory or music) or a really huge public library? That would help.

How good are you with foreign languages? One idea is to look at motets. Motets were arrangements where a composer took approx. three folk songs and combined them. You could sing the songs one at a time. However, when I looked up motets on the net, most were in foreign languages.

Other possible keywords: Machaut, Cantiga, troubadour, trouvere, madrigal

If you want to pin the music down so as to learn it, you either need to make copies from a book or to buy music software so you can download the MIDI file. Better yet, persuade a fatter cat in the org to buy the music software.