I've no idea exactly how old non-starter is either, Khandro, but we have been tagging 'non' as a prefix to nouns since the 15th century, one of the earliest recorded being non-achievement. The word is commonly used in racing situations to refer to a horse which, for one reason or another, does not participate in the race it was entered for. Horse-racing has been with us for a heck of a long time, so that was my justification for imagining, at least, that it was older than Heller's novel.