По польской элективной монархии добавлю: первые выборы там фактически прошли в 1573 году (Генрих Валуа), но сам принцип выборности польских королей закрепился еще с 1386 года (выборы Ягайло). Масштаб шляхетского представительства в 1573 году был огромным по меркам эпохи - съезды под Варшавой собирали десятки тысяч человек. Некоторые историки именно это считают первым прецедентом массовых выборов руководителя государства.

Если уходить в античность: в Карфагене существовал институт суффетов, избираемых высших магистратов с функциями, близкими к главе исполнительной власти. Выборы проходили ежегодно. Карфаген - полноценное государство. Это примерно V-II века до нашей эры.

Другой пример - выборные архонты в Афинах, хотя там власть была коллегиальной и не вполне соответствует концепту единственного главы.

Зависит от того, принимаем ли мы папу за "главу государства". Конклав как формализованная процедура выборов понтифика появился в 1274 году (Лионский собор). До этого папу выбирали кардиналы неформально, после - уже по четким правилам вплоть до физической изоляции.

Если считать Папскую область государством (а она им была - с территорией, армией, дипломатией), то 1276 год (первый папа по новой процедуре - Иннокентий V) можно считать очень ранним прецедентом.

Сан-Марино! Два капитан-регента избираются с 1243 года, срок 6 месяцев, они и есть коллективный глава государства. Самая старая непрерывная традиция выборного исполнительного руководства в мире. Часто забывают об этом крошечном государстве.