I read the manual. It told me I should be able to select from some basic Playlists in the Playlists menu, but after enabling the database that menu became empty. I'll have a look at what you suggested.
EDIT : The manual doesn't even mention anything of a History tab.
EDIT 2 : So I see the options are 'most played' and 'never played' but no 'least played'. What an oversight.
EDIT 3 : For future others and search bots, the key to the answer lies here :
http://forums.rockbox.org/index.php/topic,9299.msg71647.html#msg71647Some more research will be needed when I don't have to rush to work

EDIT 4 : Don't have time to test right now, but editing the tagnavi.config (or custom) file, one can copy the fmt_mostplayed definition and simply remove the sort=inverse part, and copy the Most Played History option (in the last section of the file) and remove the playcount>0 condition. Theoretically, it should work, except playcount is sorted as 1, 10, 11, ... 18, 19, 2, 20, 21 and so on... for years old open source software, I'm surprised at how difficult this is.