Wyszukiwanie pełnotekstowe jest możliwe na tabelach typu MyISAM, a na InnoDB nie. W jaki sposób więc mieć wyszukiwanie takie jak w google mając tabele InnoDB ?

Zamienić je na MyISAM? Ewentualnie możesz sobie zaimplementować własne, jednak będzie mniej wydajne.

Kiedyś robiłem takie wyszukiwanie. Rozbijasz podaną frazę na części składowe (po spacjach i znakach specjalnych), wyszukujesz połączenia +wyraz -wyraz, cudzysłowowa etc. Następnie tworzysz zapytanie z like, gdzie wstawiasz AND, OR w zależności od + lub jego braku, NOT jeśli jest -, całość zwrotu jeśli jest w cudzysłowie.
To wszystko jednak powoduje dość długie zapytanie (tym bardziej jeśli wyszukujesz w kilku tabelach i w kilku kolumnach), czasem na prawdę długie potworki. Trzeba mieć dobrze założone indeksy żeby to chodziło jako tako.