Правильно: на пляже.
Название Халкидики несклоняемое. Корректно: на Халкидики (ср.: на полуостров), с Халкидики, пляжи Халкидики.
Предпочтительно: на пляжах западного и восточного побережья Индии.
Пляж — это географический объект. Названия географических объектов пишутся без кавычек.
Запятая нужна: обособляется придаточное предложение.