Stone might work if your railroads remain rather primitive, pre steam locomotion size and weight. Not so much along the lines of 'rails' as some sort of grooved flangeway or curb (either outside or inside the wheel line) to provide redimentary guidence. It would, in effect, be a glorified roadway. Your vehicles would be little or no different from road carts/coaches in design or weight.
If you are looking for some alternate pre-industrial forerunner to flanged wheel/metal rail technology, may I suggest stone paved roads with a roughly 5 foot wide pavement stepped up about 6"-8" higher than the sides? Wooden cart wheels could be roughly guided by this "reverse flange" while being drawn by horses. As an alternative to trying to draw wagons across sand, it might be a viable-though, again, primitive-technology.
Once powered locomotion is developed, I think it becomes as obsolete as courduroy roads...