Or should I use rel="canonical" for the promotion page?
No, only use
canonical for pages with (almost) identical content. Your promotion list page and an individual promotion are clearly different pages.
What I do is use "noindex, follow" for the links.
Is that a good idea?
I think you shouldn't disallow the indexing. Search engines can be very fast, some web pages are indexed only minutes after they were published (thanks to feeds). I think your content is valuable for users of search engines: many search engines allow their users to limit results to only pages that were published/indexed x hours ago.
So if you really don't want to keep old promotions online, you should still allow search engines to index the pages. After you delete them, you should set the HTTP headers to 404 (deleted or was never existent) or better 410 (Gone = deleted and won't come back). But you should use "unique" URLs for that, e.g. by including the publication date:
Or don't give each individual promotion an own page, but list all promotions on the brand page (
example.com/shoes/promotions/otherbrand/), which never gets deleted. If there are currently no promotions for "shoes" by "otherbrand", you would simply tell this to your visitors on that page.
I think the best structure would be the following:
example.com/shoes/promotions: a list of links to all brands (you could include the count of current promotions in parentheses, e.g.: "Otherbrand (1)")
example.com/shoes/promotions/otherbrand: a list of links to all current promotions for "otherbrand"
example.com/shoes/promotions/otherbrand/2012-10-06_discount-and-free-shipping: an individual promotion (could be deleted when it's over)