Thanks @Falco and Discourse team for the fix 
After changing slug generation into encoded, it fixed the issue of 404 topics (without the need to rebake slugs).
We still faced the issue with not found categories, I tried things on staging Discourse to make sure I don’t mess up 
Description of The Issue
- When I return the slug generation into
ascii:
The categories work again, and their generated URLs are just fine (Arabic as expected):
https://discourse.coretabs.net/c/%D8%A7%D9%84%D8%A3%D8%B3%D8%A6%D9%84%D8%A9-%D9%88%D8%A7%D9%84%D8%A7%D8%B3%D8%AA%D9%81%D8%B3%D8%A7%D8%B1%D8%A7%D8%AA
But, the generated URLs for topics are just English (despite the title is actually Arabic), e.x:
https://discourse.coretabs.net/t/5-mktbat-baythwn-mfydt-lmsharye-telym-alalt/2930/5
- When I change the slug generation into
encoded:
The categories do not work (showing Oops! That page doesn’t exist or is private.), though their generated URLs are just fine (Arabic as expected):
https://discourse.coretabs.net/c/%D8%B9%D8%A7%D9%85
And the topics are working, with their Arabic expected URLs:
https://discourse.coretabs.net/t/5-%D9%85%D9%83%D8%AA%D8%A8%D8%A7%D8%AA-%D8%A8%D8%A7%D9%8A%D8%AB%D9%88%D9%86-%D9%85%D9%81%D9%8A%D8%AF%D8%A9-%D9%84%D9%85%D8%B4%D8%A7%D8%B1%D9%8A%D8%B9-%D8%AA%D8%B9%D9%84%D9%8A%D9%85-%D8%A7%D9%84%D8%A2%D9%84%D8%A9/2930/5
The Fix
- Change the slug generation settings into ascii
- Change categories slugs into English from every category page
- Change the slug generation settings into encoded
- Now you can change the categories slugs into your language of choice