I would start out by referencing ancient maps. In ancient maps, you will often see that they are drawn from the perspective of the people who drew them putting what was most important in the middle. Persians never centered their maps on Europe and North was not always the top of the map. In your case with the sun unmoving with a seemingly magical transference from one side of the world to the other, the people living there wouldn't understand this and would likely not be able to make accurate maps as they wouldn't know where the true center is. As a result, every map would be different when drawn.
(few minutes of contemplation inserted here....sorry...I'm typing as I think...)
Ok...as travelers traversed the world, they would find that as they walked, the sun which was behind them (as for being located immediately above the center of the world/map would instantaneously be in front of them. This is the moment when they walked over the edge of the world and found themselves on the other side because they would now be facing the middle. This system would also mean that all shadows would face away from a central point in this world which is the key. In our world, Mariners would use a device (sadly the name of it eludes me at present) which measured the angle of the sun. This allowed them to calculate their position in the longitude/latitude system. My thought is that instead of the straight lines drawn vertically and horizontally across our map, they would have a series of circles centered on the point beneath the sun. The device they will use is twofold. It will possess a bubble level to ensure that when used, it is, well, level. The other component will be shaped like an "L." It will be aligned so that the part sticking up into the air will cast a shadow on the part that is flat on the ground/flat surface which has a series of tick marks on it to measure the shadow which would determine distance from the sun (we experience longer shadows in the morning and evening when the sun is in the distance) and from that you determine which ring on the map you are on (this is assuming that the sun is unreachably high...as if it isn't that high in the sky, elevation would throw this completely off and it wouldn't work at all...). The tick marks closest to the corner on the device would have to be closer together than the ones further away and the degree of this would be based on how high your sun is in the sky...I know this much but not the specific math that would determine it...would be a bunch of trigonometry and utilize Pythagorean Theorem...
This is great and all; however, we are only halfway there. I've only placed us on a 360 degree ring a certain distance from the sun-point.
You've already said that the night sky is ever changing which eliminates star navigation...
The only thing that I can think of is that you would need a secondary fixed point that was ascertainable to everyone at all times (magnetic north on earth). With this point, one could determine a degree of angle (with a compass - the kind you used in geometry class) between the sun-point and that fixed point. There would only ever be four locations on the map that would share that particular angle. When looking at a map, one could easily eliminate two due to knowing which of the two points was on the left and which was on the right. The third would be eliminated by knowing your distance from the sun-point.
That's the best I can come up with. Either you need to add a magnetic point within your world or something that would be visible from most all locations.
If not a single point, I would say that there would need to be some kind of key points like a lonely mountain/tower/smoking volcano scattered about throughout your map so that they could be used as fixed points. I understand that there would be certain areas that would be impossible to determine location within and as such, roads would likely be made through forests or mountains which would be drawn onto maps so that travelers could find their way from one mappable location to another.
Hope this helps!!!