Как постепенно внедрять vue.js?

Стандартный подход - вы передаете данные, данные попадают в компоненты, которые их соответствующим образом отображают.

С аяксами достаточно просто, я использую библиотеку axios.js.
Я сейчас тоже перевожу свой проект на vue, постепенно его изучая. Все, что можно, отдается по ajax, все что должно быть в рамках SEO, отдается со стороны сервера, со стороны vue, использую привязку к модели или вызовы по v-click и подобным. Для какого-то интерактива, использую пользовательские директивы. Например кастомная директива связывает конкретный товар из списка товаров с его показом, если он есть в корзине, которая загружается по аякс. В общем, сначала ломал себе мозг, как связать список товаров на странице с корзиной, вот нашел очень хорошее решение -пользовательская директива, и для СЕО хорошо, и интерактивно в обе стороны, и с элементом можно творить все что угодно.
Сейчас делаю пользовательскую директиву, которая подменяет href в ссылках пагинации, на параметры фильтров, которые рисуются через компоненты vue.

Переводить сайт на vue можно по частям, я бы даже сказал, что нужно по частям. В большинстве случаев нет смысла делать чисто одностраничную SPA с одним глобальным vue-приложением - проблемы с индексацией поисковиками, другой непривычный UX для пользователей, вот это всё. Выделите места, где нужна активная интерактивность и их сделайте в виде приложений vue. Начальные данные можно получать не аяксом, кстати, а помещать при генерации страницы на бэкенде в глобальную переменную window и потом в приложении vue их оттуда забирать в beforeMount(). Пример можно посмотреть здесь в readme: https://github.com/spatie/laravel-blade-javascript... . В этом случае пользователь будет избавлен от необходимости после загрузки страницы смотреть на индикатор загрузки данных аяксом.

А при аякс-запросах, конечно, надо делать вариант 2. Пот бэкенда только json, никаких скриптов - запутаетесь. Также заранее ознакомьтесь, зачем полезно нормализовывать данные для хранения на клиенте, когда-нибудь точно пригодится - https://habrahabr.ru/post/332628/ , https://github.com/paularmstrong/normalizr

vuex, кстати, использовать можно только если у вас есть зависимые друг от друга приложения (например, приложением сделан сайдбар, где должны меняться числа после действий пользователей). Если такого не нужно, то можно обойтись и без него.