Когда устанавливал ОС, для boot-раздела указал размер 500М.
У меня /boot тоже 500МБ. Просто удаляю старое ядро в Synaptic, после получения нового. Времени занимает минуту.
Можно ли увеличить этот размер без потери данных?
gparted не дает возможности изменить размер этого раздела.
Для того, чтобы увеличить /boot, нужно уменьшить раздел следующий за ним. Хорошо, если этот раздел /swap, и хорошо если все разделы были размечены как "основные". Тогда без проблем.
Если первый раздел /boot размечен как "основной", а все остальные помещены в "дополнительный", тогда увеличить его без их удаления не получится.
По поводу того, что все действия надо производить из-под Live-CD, уже сказали выше.