Retrive specific deleted nodes and re-import
We had this same problem on one of our sites and the best solution we could come up with was to use Node Export as you mentioned. Like you, we didn't have it or UUID installed at that time, but we installed them just for this purpose, and it worked fine.

The only catch is you need to be able to load the backed-up database into a functioning site (we did it on our test server) before you can export the missing nodes.