If we didn’t have a minor education requirement (minor because high school is free and is seen as the basic education that everyone has), then an age requirement can be substituted. For example, invoking the current age requirement of 35 to become president if you do not have a high school education so at least we know that you have life experience as a substitute.
As for the criminal requirement, felons already can’t vote and participate in the electoral system so it’s questionable that many would accept felons being “randomly” chosen to lead the country. One could easily imagine and protest that a mafia kingpin who wins office by random chance did so by subverting the lottery. True or not, it’s believable enough to destroy legitimacy and throw the country into chaos.