Every document will need to be opened, updated and saved for this to happen but it doesn't have to be done manually and may not be even be required to happen via a batch macro.
At its simplest you could add this macro to your Normal.dotm template (It has to be placed in the ThisDocument module). This will then run automatically as YOU open any existing document to import the style definitions from YOUR Normal template.
Code:
Private Sub Document_Open()
ActiveDocument.CopyStylesFromTemplate NormalTemplate.FullName
'ActiveDocument.CopyStylesFromTemplate AttachedTemplate.FullName 'a better alternative?
End Sub
It doesn't matter that thousands of documents don't have the right styles if EACH one is updated as it is opened. Over time, you will gradually update them as each one is opened and you won't realise they aren't all already updated.
Now, having said all that I will now recommend you reconsider if Normal.dotm is what you truly want applied in all cases. I am a true believer in the power of templates and Normal.dotm is rarely the basis for styles in my documents. I STRONGLY recommend that users make use of different templates for different purposes - style definitions should vary according to the document type eg letters/memos/reports/user guides/posters because each document type requires different layouts. The disabled line in the code above provides an alternative option that might be a better fit for your requirement. If the document has Normal as its 'Attached template' then it has the same effect as the enabled line of code but if a purpose-built template was used then you won't be breaking with this alternate code.