Du bör antingen använda fulltextindex (du sa att du inte kan), designa en fulltextsökning själv eller ladda ner sökningen från MySQL och använda Sphinx/Lucene. För Lucene kan du använda Zend_Search_Lucene implementering från Zend Framework eller använda Solr.
Normala index i MySQL är B+Träd, och de kan inte användas om början av strängen inte är känd (och så är fallet när du har jokertecken i början)
Ett annat alternativ är att implementera sökning på egen hand, med hjälp av referenstabell. Dela text i ord och skapa en tabell som innehåller word, record_id. I sökningen delar du sedan upp frågan i ord och söker efter vart och ett av orden i referenstabellen. På så sätt begränsar du dig inte till början av hela texten, utan bara till början av det givna ordet (och du kommer att matcha resten av orden ändå)