Можно установить через WUBI как обычную программу в Виндовс (см. Википедию) в случае с Убунту, как с остальными не знаю. Но WUBI -- плохой вариант, это исключительно чтобы попробовать; на NTFS работа нестабильна.
Форматировать всё не надо, надо выделить раздел диска (только часть) и уже его форматировать в ext3, ext4 или reiser4.
Вот Вам сслылка на всякий случай, написано для Убунту, но принципы применимы для всего:
http://help.ubuntu.ru/manual/разметка_диска И далее тоже читайте, особенно
http://help.ubuntu.ru/manual/установка З. Ы. Насчёт доступа из Линукса в NTFS не волнуйтесь так :-)
Всё прекрасно работает.