How do I change the default track in iTunes?
iTunes starts playing what is currently selected. For me for instance the playlist selected was "Most recently added", so when I hit the play button on the keyboard, the first song from this list starts to play.

The only way I know of to solve your problem is to enable random play in iTunes.
This is easily done by clicking the snaked arrow button next to the cover image in the top view. If it's highlighted blue, random play is on.
Quitting iTunes and hitting the play button again will play a random song from the library.

Drawback: Whenever you changed that (because you don't want to have random play but want to listen to an album) you have to remind yourself to enable it again before closing it.

AFAIK there's no preference setting for that.