I'm looking for a music software that is able to compose (random) solo melodies along a given chord progression using corresponding scales.
The Mac software suggested by VAlexander looks very interesting and is certainly worth mentioning for future readers. Unfortunately, in my case it's the wrong platform. I forgot to mention that I am looking for a Windows, Linux, Android or web-based application or alternatively a java library.
It does not require a full-feature music sequencer. A smart little tool would be totally sufficient.
The tool that I've found and described in my answer provides reasonable results, but I am still very interested in software, that addresses the same task with alternative concepts. I leave the question open therefore.
The output should be in MIDI format.