I do the following in my Pre-Calc and first-semester Calculus course:
Assignments: A week's worth, so usually 3 sections with 8-15 problems per (depending on difficulty).
Homework Day: About once a week, students are called randomly to present* their solution on the board to an assigned problem. About third to a half of the problems are pre-selected (by me, unknown to students) to be done this way.
* Here "presents" means writes a full complete solution on a section of the board that can be understood without any additional verbal exposition (though I sometimes ask clarifying questions).
Random Method (Concept): Conceptually the idea is that at the beginning of each Homework Day, every student's name is added into a hat. Names are drawn one by one and we go down a sublist of assigned problems. For students whose names are not called that period, their name remains in the hat so that next time (after adding everyone's name again) they will be in there twice, and so on.
Random Method (Implementation): I do all the randomization using Mathematica to manipulate a list of student names and a list of problem numbers. This is then printed off and I just read down my list. The "hat" is a Mathematica file that I update throughout the semester.
Adjustments: Sometimes if I have a lot of left-over names already in "the hat" I won't add everyone's name again. But I don't tell the students this. If I have more problems then students (which happens in smaller classes) then I'll add names twice.
Results: Every student has a possibility of getting called on at least once, so all are motivated to be ready. Also, every time a student doesn't get called on, they are more likely to get called on next time. I have had students go 3 or 4 times without getting called and then for the next couple Homework Days they end up presenting multiple times each day. The longer they go without presenting, the more ready they realize they need to be. In a semester with 13 homework days and ~25 students, by the end everybody has presented about the same number of times, maybe +/-2.
Grading: Since not everyone presents the same amount, points are given out of the number of times they were called and then this percentage entered for the homework grade. Also, since I really want students to show work so we can learn from it, the rubric is as follows: 4 pts for a solution (even if wrong), 3 pts for a solution to a different assigned problem (with permission, even if wrong), 1 pt for being there, 0 pts if absent.
Extra Credit: Some homework problems are hard and students need to pass. If 4 students in a row pass and/or ask to do a different problem (for the deduction), then the hard problem becomes extra credit and I ask for a volunteer. This is no longer random.
Additional Notes: This is way better than grading papers and it seems to benefit students more or by the same (but certainly not less). It's good for classes were the concepts are really new (e.g. Calc I, Pre-Calc, even Number Theory), but I wouldn't recommend it for classes where the problems can be long, tedious, and/or computationally heavy (Calc II, Diff EQ, Linear Algebra).