How to create a block with taxonomy terms and their corresponding nodes?
Well you need to use views_field_view module. In you views :


Create a view of Taxonomy type
Add a filter of Taxonomy Vocabulary = Categories
Add filed Term: tid (exclude) and Term: Name
Add Global View field pass argument tid (Another view in which contextual filter of tid is added and 3 items are displayed in views configuration)


Done.