Already in the 15th century Johannes Ockeghem wrote the mass Cuiusvis Toni which was written in such a way that it allowed the singers to decide in which mode to sing it (I am referring to the Gregorian modes: Dorian, Phrygian, Lydian or Mixolydian). Quite a counterpoint challenge.
During the 18th and 19th centuries it was common in Europe to play constructing musical pieces from a series of very short fragments. Rolling dice decided which of the fragments were used and in what order. The most famous example is Musikalisches Würfelspiel by Mozart.
In the second half of the 20th century the use of random procedures was much more marked. There are even different branches of aleatoric music. In Music of changes, John Cage uses the book of the I ching to construct the piece. The resulting score, however, is traditional. The pianist has well noted both the duration values and the pitches.
Many of the pieces of aleatoric music have an open form. In Klavierstuck XI composer Karlheinz Stockhausen lets the pianist decide which fragment to play although each fragment conditions the character of the next one. In Zyklus a percussionist has to decide which way to read the score starting from anywhere.
Sometimes random procedures are used statistically. Sound mass music is constructed from many, many slightly different individual behaviors that together present an average sound. Perhaps the best example is Gyorgy Ligeti's Symphonic Poem for 100 Metronomes although it is not very aleatoric.
The musical games I work on can be performed by people without formal musical training and produce stochastic pieces with textures typical of sound mass music. Ligeti seems to have been the first to propose a piece giving instructions in 1961 when he made the audience sing at an event by writing on a blackboard.