Это очень легко делается с помощью макросов, а вот с помощью формул даже и не представлю сразу. Здесь нужны циклы, которые по факту (кроме циклических ссылок) нельзя реализовать.
Еще один способ обойтись без циклов - попробовать ветвление с функцией "ЕСЛИ".

Как вариант можно построить подобие таблицы умножения, но в таком случае надо будет повторить эту операцию дважды: вначале собрать И+О, а потом Ф + (И+О). Сейчас не могу приложить файл - на работе.
В общем случае, чтобы потом избавиться от "тела матрицы" можно использовать сводные таблицы.

Это похоже на подбирание кода.

Владимир, это называется не подбирание кода, а алгоритм брутфорса (грубого подбора) → http://ru.wikipedia.org/wiki/Полный_перебор
Еще хотел бы сказать, что впечатлен этажностью решения. Это ж какую надо выдержку иметь.  

Ну формулу можно было бы и покороче составить (раза в три), к тому же не массивную и автоматически подстраиваемую по количеству значений в столбце A

Коллеги, считает не совсем корректно, вернее, считает то нормально, но только для __идеальных__ входных данных, как в первоначальном примере.
К сожалению, я не учел некоторые детали в первоначальном ТЗ.

Попробовал поковырять формулы Владимира и МСН -- либо ошибки, либо неверная выдача. Своих знаний никак пока не хватает.

Ошибки отработки формул:
1. входные данные должны быть разделены по отдельным колонкам, как в моем примере, (а не как вы предложили, в одной)-- т.к. в качестве входных данных также выступают и фразы. Поэтому, даже если я объединяю свои входные данные в одну колонку -- то сейчас формула не корректно отработает, т.к. сейчас в вашем варианте решения разделителем выступает пробел.

2. Если на входе число колонок (слов) отличается от трех в любую сторону, то тоже формула не работает (причина, думаю, та же, разделитель -- пробел)

3. Первая колонка (фраза или слово) -- всегда на первом месте, тогда как мне надо получить все варианты (любая фраза из любой колонки на первом месте, на втором месте, на любом месте)

Уточненное ТЗ
Входные данные
1. На входе может быть 2-10 колонок (или n колонок для общего случая)
2. В каждой колонке содержится текстовая фраза
3. Каждая фраза состоит из 0-10 слов (или m слов для общего случая), во фразе могут быть цифры 0-9 и числа, знаки препинания .,!?, скобки (), кавычки "", дефисы -, слеш прямой и обратный /\, двоеточие :, точка с запятой ;, и т.д. Словом, любые знаки препинания и пунктуации (любые символы с клавиатуры)
4. Колонка может содержать пустые ячейки
5. Число строк с фразами в каждой колонке различно

Выходные данные
1. Одна колонка -- фразы, вторая колонка -- длина строки.
2. Каждая фраза комбинируется с каждой другой фразой, каждая фраза должна побывать на 1, 2, 3, ..., n месте.
3. На орфографическое и грамматическое несоответствие слов между собой не обращаем внимания. На итоговый порядок знаков препинания -- тоже.
4. Итоговый список отсортирован по возрастанию длины строки.

Если решение можно формулой -- лучше формулой, что бы я смог хоть как-то подразобраться. Или скрипт=)
Я прикрепил новый пример.
Сори, что написал и сюда, и на excelworld.

Товарищи знатоки, тут несколько строк по три слова. А если у нас 1 столбец с 60-ю фамилиями и второй - с 80-ю именами? А вывести надо в третий столбец ВСЕ варианты фамилия ПОТОМ имя? Или же один столбец - фамилии, а другой - имена, ВСЕ варианты? Второй вариант даже лучше.
И как сделать, чтоб количество исходных вариантов фамилий и имен программа брала из отдельных ячеек (они постоянно меняются при каждом новом расчете).

Устроит любой вариант: формулы, макрос... лишь бы работало.

У Вас вопрос по этой же теме? Где тогда Ваш файла-пример?

Power Query.

Не, Power Query несколько другое.