After deleting an app, can you (much) later reinstall it and restore its data from iCloud?
The answer is yes and no.

What happens quite easily after a restore (for example after an update) is that iTunes restores the save data for all applications, but not the applications themselves. Therefore as soon as you install them, the old save games will be available (this applies to all apps, not just games). Just by itself nothing will be saved without backup.

BUT: If the application supports iCloud sync and stores it's data in iCloud (which has to be explicitly supported), your data will be still available after deleting and reinstalling the app. 

In short: You should be really careful and unless you're absolutely sure the application in question does support iCloud for your saved data, don't delete it without backup.