my client wants to send automatically a newsletter every time a new product is added. The newsletter should be segmented by categories and stores, so the user has to choose which would subscribe. Is there any plugin/module as starting point?
If you are simply wanting to add a link to the product into the newsletter then you can add a new newsletter template, then insert into this template using the cms widget "Catalog Product Link" you can add a link to a product. This is the same as adding a link to a product via a cms page or block.
If you are looking at sending a product list then I would suggest looking into how the widget "Catalog New Products List" works. You could extend this to take a list of product ids that need to be included in your list.
A nice example is the block Mage_Catalog_Block_Product_List_Random here is just makes a list of products randomly but you could add a products ids attribute and then create your own _getProductCollection
or follow this article
Answer is here https://stackoverflow.com/a/3817882/3154984
On both module description I didn't see any thing related to new products notifications.