На острове проживают 1234 жителя, каждый из которых либо рыцарь (который всегда говорит правду) либо лжец (который всегда лжет).

Нет, не могло.
Предположим, что описанная ситуация возможна, тогда, каждая из фраз произнесена по 1234 : 2 = 617 раз. При любом разбиении жителей на пары существует только три возможных вида пар: 1) два рыцаря; 2) два лжеца; 3) рыцарь и лжец. В парах первого и второго вида каждый произнес: «Он – рыцарь!», а в парах третьего вида каждый произнес: «Он – лжец!». Таким образом, каждая из фраз произнесена четное количество раз, что противоречит тому, что их должно быть по 617.