I don't know about many other regions, but around here, it is a fairly common occurrence for students to enter high school not knowing how to add two fractions, so if we're going to rebuild high school, we may as well rebuild get them prepared for the new material while we're at it!
I agree with many of the points in Lockhart's lament, however I believe there is still a large necessity of getting students comfortable with all the basic objects, which can only really be done with a combination of exploratory exercise, and the standard "worksheet of 50 exercises". On top of this, I believe basic algebra should be moved fully to the elementary school level (no middle school around here, so elementary goes to grade 7) freeing up more space in the high school curriculum.
I think the basic concepts of most first and second year undergraduate courses should be introduced at different times. For starters, basic logic in an abstract setting in elementary school (students scoff at you if you ask them why one car being blue doesn't imply all cars are blue, yet when you replace the visual part of the example, with functions and variables, are utterly lost), and proofs at least in early high school (contradiction, contrapositive, why converse can not be used, etc..). Elementary number theory and simple counting arguments can be taught right away, with divisibility, congruences. From here, one could create two streams; One stream involving math for people who just want to be functional, and math for those who want to see math! We shouldn't force math onto students if they truly don't find it interesting, nor should we prevent the neat stuff from being taught just because it's not a topic everyone will enjoy. From here, with these basics complete, we could introduce groups (..and rings and fields) with plenty of examples available. From here, vectors and matrices over $\mathbb{R}$ could be introduced, to provide even more examples of groups, while also displaying many simplified examples of real world situations using linear algebra. The idea behind the construction of $\mathbb{R}$ from $\mathbb{Q}$ (though no need for rigour) and the algebraic closure of $\mathbb{R}$. Again, no great rigour needed, but see if they can find something "missing" in $\mathbb{C}$ that may perhaps lead to another space. It would also be nice if throughout all this we could engage the students in "small" computational experiments.
All the while, it would also be great to explain what's out there in math. For example, mention there is an object called an elliptic curve, which just so happens to be a group if you look at it right. These curves are being used in modern cryptography, proof of Fermat's last theorem, and have many puzzling features to be discovered. Any high school student could understand that sentence, and it gives an idea of why we are doing this! (During my undergrad, one of my old friends from high school was actually under the impression math had been solved, since we were never lead to believe otherwise!!)
Now, this is certainly a perfect world I'm describing. Obvious problems I see are
-If we are to teach more advanced concepts (well) in high school, then high school teachers need to be comfortable with these concepts. Preparing all our teachers for this is no simple task.
-Even if a curriculum with all this were installed, with teaching staff ready to go, the enrollment would surely not be very high. If you tell students they can get through life perfectly well with 'easy' stream, you would have a hard time convincing most students (apart from scholarship hopefuls and those already fond of math) it would be worth their time to learn all this extra material. With enrollment very low at smaller schools, the extra funding required would be very difficult to justify to government officials with no background or fondness in these concepts.
Edit: As I'm just seeing other comments now, I feel I should mention probability and statistics are covered were covered in my high school curriculum, however if they are not being covered, this would fall in both of my mentioned streams! People should definitely know how to read articles in the newspaper with study results.