You have mostly answered your own question within the question itself. In fact, you did so near the end, using some of the same ideas that I was thinking of as I read through it.
First a nod to similar real situations
There have been many settlements, cities even, located in deserts, even in ancient times.
Check out Palmyra, Masada, and even Egypt (an entire nation, not just a city). There are many other groups of people who have lived in the desert and established villages or cities around water sources.
Some of them, even in old times, extracted their water from underground. We need to rid ourselves of the false notion that desert means nothing but sand everywhere and nowhere for water to collect. Even in the middle of a desert it is possible to dig wells. You can even keep the "desert is a bunch of sand" notion for most of the desert for visual effect but have other formations interrupt it, or have the sand be only so deep and water collecting underneath.
Palmyra was more like the city in your setting, connecting the lands on the opposite sides. The linked article above talks about how the city was on a trade route between them and how it was a cultural blend.
Masada is known more for its defensive capabilities, and indeed it was famously used for protection. Not the same as your situation, but it demonstrates the ability of people to live in the desert. Your people would have it much better than Masada in a lot of ways, not just the lack of war.
Egypt is a great example for your consideration because it was made possible by the Nile river. The Nile river would periodically flood, watering an even larger area, but also people would redirect some of its waters where they needed. This is a great parallel to what you could do with your lake, especially if you included any rivers flowing into or out of it.
Water
They have a lake nearby, good. Make sure the lake is big enough to supply all the water needed and that the lake itself gets resupplied somehow, then water is covered. The answer to the lake water needs to be more than a simple "'Cuz rain" since it's in a desert. I thought of a river, but then you get the question "Why don't people live all along the river, or better yet come down the river by boat instead of walking the desert," so the water should come from underground or the river should not reach to waterways that extend by rivers or oceans to the rest of the world.
If the underground water is merely an ancient, trapped reservoir then it will eventually be depleted. You can either use this to supply a crises at some point, or you can say the underground water is a flow of water such as an underground river. The people living in the city might not even know where the water comes from; they don't need to know that the underground water flow exists.
If it is an above ground river, think of the Mississippi river. That starts off as a lot of very tiny streams of water at higher elevation which keep combining until they form a huge river. In your case, the Mississippi river would reach to the end of your desert, so you either need to decide that this is fine, that the waters come from outside the desert, or you need to scale it down. I would suggest that you have tiny tributaries just outside the desert feeding into it and merging farther into the desert. The smaller waterways could be unusable by boat, and you could have a stretch of large river that is anywhere from 100 to a thousand miles long in the middle of the desert that empties into the lake. With this option, most of your farming would take place along the river leading to the lake, and the trees could grow around the lake.
Food and building supplies
Both the food and building supplies come from growing plants.
Even if the people do not need as much food or water as we do, as you claim, they still likely need more than "a few trees." Fortunately, you have a water source that you can use for farming. If fed by a water flow, either above or below ground, you can make the amount of water be anything you want, so you can make the lake it empties into support any amount of trees or farming that you desire. You could have 100 trees or even a thousand or more, heck, you could have a forest in the middle of the desert, a forest fed not by rain but by the water that comes in underground into your lake.
The people probably irrigate and grow whatever crops they desire, and they probably tend to the trees to make sure they have enough for what they need.
So your people have food, water, and they have shelter and whatever else they can make out of wood. Sounds like you're set as far as survival is concerned.
Medieval setting tools
For other things beyond survival, such as iron tools, they can trade for those. This will work even with the very irregular contact with the outside that you specify as iron tools can last a very, very long time. I still use some tools that belonged to my grandfather, and I don't know if he got them new or if they were passed down to him too. Iron tools can last hundreds of years if they are not left to rust.
People
In order to have a city, you also need people, obviously. That is an easier part; you can just say that the road came first, built by the nomads who crossed the desert, and the city sprang up later when the lake and the few original trees around it were discovered.
Note that the city probably started as just a few people staying near the lake they found and starting to garden at its shores. As those few people developed the land by irrigating and planting more trees and vegetables and building some permanent buildings, then other nomads may have joined them. Usually breaking the habits of those around you (in this case, being nomadic) is done by few people, then later others join them if they prove successful.
And now you have everything you need available to the middle of that desert for a medieval setting.
