Gallery block inside a Matrix
I guess it depends on what information each Asset needs to contain. As you mentioned, a Matrix within a Matrix is not possible, so you will need a different method to attach additional information to each Asset.

One method that may work is to create Asset Meta Fields for Assets. This way, you can define additional things on each image on the Asset level. For example, you could have custom fields for things like title, description, copyright, etc.

With Asset Meta Fields in place, you could define one "Gallery" Matrix block that allows for multiple files to be selected. The order could be controlled by drag/dropping each of the selected Assets.