You have to re-deploy the items, disregarding whether you use TDS or not. Security settings for items are stored with items in Sitecore architecturally, that's why if the security settings are changed for an item, this literally means the item has changed and should be re-deployed.
In order to minimize the amount of items you have to deploy each time you can:
- leverage the "inherit" option as much as possible - as a result, only items with explicit 'allow' or 'deny' permissions are affected
- assign security for roles, not for users - as a result, in order to apply permissions for a new user you simply include it into the appropriate roles