The earliest reference to a prayer similar to אין כא-להינו is found in Heichalot literature. That is literature from the Talmudic period and beyond that dealt with the workings of the heavenly world. Meyer Bar Ilan in his book סתרי תפילה והיכלות מאת מאיר בר-אילן (1987) reproduces this prayer:
The prayer is similar to our version but provides the opening words of the lines in a different order. However, if you think about what makes sense, then the Heichalot version is superior because it begins with questions which are answered in the subsequent lines. The current version, on the other hand, places the line with the questions after providing an answer. Why was the order changed?
Professor Bar-Ilan points to an answer provided by the Machzor Vitry:
מחזור ויטרי סימן קלד-לכך אנו אומרי' אין כא-להינו בשבת. שיש בו ד' פעמים אין. ד' פעמים מי. ד' פעמים נודה. שהן י"ב פעמים. כנגד י"ח ברכות שבכל יום. ועוד ברכת המינין שתיקנו ביבנה. הרי י"ט ובשבת אין אנו אומרים אלא ז' ברכות. נמצא י"ב ברכות חסר תפילת היום מחול. כנגד י"ב ברכות החסירות אמרי י"ב פעמים אמן. אין. מי נודה. ולבסוף ברוך אתה. נראה עתה כאן י"ב פעמים. ברוך אתה. אמן. והן י"ב ברכות.
Translation: For this reason, we recite Ain K’Elokeinu on Shabbat. In that prayer we say the word Ain 4 times; Mi four times and Nodeh 4 times. (The Aleph, Mem and Nun that begin those words together spell out Amen). Those letters are said a total of twelve times. We say them to correspond to the 18 Brachot of Shemona Esrei which now total nineteen Brachot since Birkat Haminim was added at Yavne but on Shabbat we only recite seven Brachot in Shemona Esrei. That means that we are short twelve Brachot. To make up for the missing twelve Brachot, we spell out the individual letters of Amen twelve times-Ain, Mi, Nodeh. At the end we open one line with Baruch and a second line with Ata. So we end up with saying twelve times Baruch Ata Amen. That produces the twelve Brachot we are missing.
I would like to suggest an alternate explanation which is based on an excerpt from a Siddur that represents Nusach כפא (Crimea, 1803).
The order of the lines may have been changed to the follow in poetic order the lines of the Piyut that precedes אין כא-להינו. Coincidentally the opening line of the Piyut, 'אין קדוש כה is a line some say just before reciting אין כא-להינו.
One more point about the excerpt from Nusach כפא. It provides that the Piyut only be said between Pesach and Shavuot. That means that they believed that the Piyut should be said during that period as part of our preparation for Matan Torah on Shavuot.