If I change my Apple ID's country, would I need to re-download everything in order for all my apps to update naturally? Let's say I decide to change the country in my Apple ID, and I only have free apps that are available in both my previous and target country. Would I need to re-download everything in order for all my apps to update automatically?
Would all my previous apps be considered to be from the previous country?
Changing to a different country would not matter for the apps in the scenario you described. Your apps would continue to update fine and you need not re-download anything.
An app developer can choose what territories their apps are made available in. So when you switch to a different country, the same app may not be available.
But as long as the app is available in both the countries, you will be fine and receive the updates normally. If the app isn't available in the new location, it will stay installed and then never update / download from iCloud / App Store until it is available for your country or you switch back.
Unless the app actively checks for this, things work - but it's really up to the developer how urgently they check for App Store receipts - the operating system doesn't force a check the moment you change and instead waits to check the next time an update or install happens.