Ну... форматнуть можно live-cd линукса. Практически любым. Если в консоли делать, то можно от той же gentoo взять - 100 метров, примерно. Затем из cfdisk переразбить диск. И форматнуть раздел. Либо можно просто удалить все разделы и с лайва винды его форматнуть (просто по опыту - не все линуксы нормально делают NTFS). Если хочется мышкой - можно ту же убунту качнуть. Или кноппикс. Или инсталлятором того линукса, что у тебя был.