In a couple more years he'll be ready for
One Thousand and One Nights (or Arabian Nights, as it is more often known), or at least for many of the stories. Some are a bit racy, so make sure you read them yourself first (if that's an issue). Four (nearly five) is probably/maybe a tad early, but considering how intensely I enjoyed those stories myself around that age I really can't recommend
One Thousand and One Nights highly enough.
Unless you specifically want only religious children's stories, I also suggest
Norwegian Folktales (collected) by Asbjornsen & Moe. At least I can't remember there being any religious content to the tales, but on the other hand they're chock-full of trolls, witches, beautiful princesses and much, much more.
The Brothers Grimm and H. C. Andersen's collection of folk and faerie tales you probably already know about and they, of course, are also not of the religious persuasion. Great stories though...
Lastly you may want to look through the collection of books in the
Pantheon Fairy Tale and Folklore Library at Amazon, which contains faerie tales from far and near, East and West. They're not collections of
religious children's tales, but obviously the the local religion(s) colour the tales.