My feature includes custom code, some views, content types and a taxonomy vocabulary.
An overview page should list all contents grouped by their taxonomy term (tag). The first group should be "not tagged".
How do I add the "not tagged" group?
not really sure how you're getting your lists, you mention custom code, and views.... if you just need a list of nodes that have no taxonomy term:
$nodes=db_query('SELECT * FROM node AS n LEFT JOIN taxonomy_index AS ti ON n.nid=ti.nid WHERE ti.nid IS NULL')
will give you that.
you could add a join to the taxonomy_term_hierarchy table and a WHERE clause to determine if the node has a term associated that is part of your vocabulary