Перечень документов, которые вы обязаны предъявить при заключении трудового договора, определён ст. 65 ТК РФ. В этом перечне указаны только паспорт (или иной документ, удостоверяющий личность), трудовая книжка и (или) сведения о трудовой деятельности, а также в отдельных случаях документы воинского учёта, образования, справка о судимости и т.п. — но согласие родителей в нём не упоминается. Поскольку вы уже работали ранее, у вас есть трудовая книжка, которую вы предъявили на предыдущем месте работы. Требование нового работодателя принести дополнительное согласие не основано на законе.
Статья 65. Документы, предъявляемые при заключении трудового договора
Если иное не установлено настоящим Кодексом, другими федеральными законами, при заключении трудового договора лицо, поступающее на работу, предъявляет работодателю:
паспорт или иной документ , удостоверяющий личность;
трудовую книжку и (или) сведения о трудовой деятельности
— Трудовой кодекс Российской Федерации, ст. 65 (в ред. от 01.12.2014)
Что касается медицинского осмотра: ст. 266 ТК РФ устанавливает, что лица до 18 лет принимаются на работу только после предварительного обязательного медицинского осмотра. Это обязательное требование, не зависящее от согласия родителей. Вы как 16-летняя должны пройти такой осмотр за счёт работодателя, и именно этот документ (результат медосмотра) работодатель вправе потребовать, но не согласие родителя.
Статья 266. Медицинские осмотры лиц в возрасте до восемнадцати лет
Лица в возрасте до восемнадцати лет принимаются на работу только после предварительного обязательного медицинского осмотра и в дальнейшем, до достижения возраста восемнадцати лет, ежегодно подлежат обязательному медицинскому осмотру.
Предусмотренные настоящей статьей обязательные медицинские осмотры осуществляются за счет средств работодателя.
— Трудовой кодекс Российской Федерации, ст. 266 (в ред. от 25.11.2013)
Необходимость согласия родителей не зависит ни от вида работы, ни от региона: федеральный закон (ТК РФ) устанавливает единое правило для всей территории РФ. Ваш предыдущий опыт работы в другом городе без согласия абсолютно законен, и это подтверждает, что для 16-летних такого согласия не требуется. Отсутствие согласия родителей не может быть основанием для признания трудового договора недействительным, поскольку оно вообще не требуется по закону. Если работодатель настаивает на своём требовании, вы можете сослаться на ст. 63 и 65 ТК РФ и попросить письменный отказ — это будет нарушением трудового законодательства, и вы вправе обжаловать его в трудовой инспекции или суде.