This cannot be done with smart playlists (yet). Although you can create your own smart playlists, all criteria only match directly to a song from your database. Any comparison between found songs or grouping of matching songs is not possible. At most you can edit the smart playlist for "never played" to order songs by album (of course only the not yet played ones)
Looking at clementine's database at ~/.config/Clementine/clementine.db
it seems, that clementine essentially manages all songs in an single table named 'songs' (so no extra tables for artist or album). But as it is a sqlite database it should be possible to write a little program that does the appropriate queries to find albums where no song has ever been played. Something like this:
select album, track, title, playcount, filename from songs
where album in (select distinct album from songs where playcount = 0)
and album not in (select distinct album from songs where playcount != 0)
order by album, track;
From this list a playlist could be generated. I'm not sure about directly inserting it back into the database, but exporting a .m3u or .pls should be possible.
A possible problem could be that several artists could have albums of the same same as well as there could be albums with several artists on them. So separating albums could be an issue.