ネギトロ巻きの誕生は、1964年（昭和39年）、浅草に本店がある『金太楼鮨』とされる。三ノ輪店で残った寿司種を手巻き寿司にして賄いで食していたが、鉄火巻きに使用する中落ち・すき身にネギを加えると、マグロの脂っぽさが打ち消された。それを客に提供したところ好評で、常連客を通じて本店にも伝わり、本店のメニューに採用された。

偶然にできた寿司ネタ「ネギトロ」その由来の秘密（週刊現代） | 現代ビジネス | 講談社

ねぎとろ発祥の店と言われているのが、東京浅草に店を構える大正13年創業の金太楼鮨。昭和39年、当時の会長だった間根山貞雄氏が考案したという。その開発の経緯はこうだ。
同店ではまぐろを毎日大量に仕入れていたが、筋の部分は食感が悪く、刺身や寿司に使えず、余っていた。叩いてペースト状にして食べれば、脂がのってトロトロで美味いが、今度は歯応えが皆無。
そこで仕方なく、巻きに使おうとしたところ、昼食用に茹でていたそばかうどんに使うネギやワサビなどの薬味を筋の部分にぶちまけてしまう。やむを得ず、ご飯にのせて醤油をかけて食したところ、これが美味い。そこで、大当たり間違いなしと、店で出すことに決めたという。
思いがけず生まれた新しい寿司ネタ。その命名について、間根山氏はこう語っている。
「浅草には『麦とろ』という名前のとろろ飯を売る店が戦前からあり、専門店としては珍しいので土地では一応知られていた。よし、これだと、麦とろ→ねぎとろと語呂を合わせて決定した」

というわけで、この説明によれば「葱」＋「（麦）とろ」である。

例の「チコちゃんに叱られる！」でもこの説が採用されたらしい。

ただし、この説明が本当に正しいかは分からない。

牽強付会な印象も無いではないし、「銀ブラ＝銀座でブラジルコーヒー」のように店が積極的にデマを流している可能性もある。

この場合は、昭和39年（1964年）以前に「ねぎとろ」という用例があれば、金太楼鮨の説明は疑わしいということになるはずだ。

が、そう都合よく見つかるはずもない。誰か探してくれ。

追記。

国立国会図書館デジタルコレクションで検索した。

1972年 12月の『食の科学』。

青ジソは香りのよさが好まれてよく使われ、イカのにぎりの場合など、一葉添えられることが多くなった。この青ジソの葉を細く切っていりゴマを加えた、シソ巻ずしを台東区東浅草の金太楼鮨でやっている。また、生ネギとトロとを巻いた「ネギトロ」も、ここの名物である。生ネギをすしに使うなどはなかなか思いつかないことなのだが、このネギとトロというのが相性がいい。

1973年 4月の『週刊文春』。

浅草の東、鮨·金太楼本店。（中略）「ねぎトロ」が日に、キロ以上とれて、さばけて行くのですからご立派。ちっと解説させて頂くなら、ねぎトロのトロとは、まぐろをさばいたあと、皮や骨についている肉をこそげ取った身を寄せ集めたものです。（中略）ねぎトロは、いまいったトロにきざんだねぎを混ぜ、ゴマを加えたもの。

1975年 1月の『信用金庫』。

信用金庫 29(1) - 国立国会図書館デジタルコレクション

先日、仕事の関係があって、浅草のあるおすし屋さんを訪ねた。そこで、ネギトロというものをたべた。たいへんおいしかったので、ほかであまりきかないけど、おたくだけのものかときいてみた。若いご主人は次のように話してくれた。そうです。実はわたしたちも、すしにネギは禁物だと教わってきたのです。ところが、ネギのとても好きなお客さんがいらして、ネギを巻いてみてくれというご注文なのです、ついでにトロも一緒に入れてくれというので、試しに巻いたのです。ところが、これがなかなかいけるのですね。それで、その後いろいろ工夫してみました。トロをよくたたいてアブラをうかし、スジをとって、それからネギと一緒に巻くのです。これをわたしのところのレパートリーに加えました。ですから、これはお客さんに教えていただいたものといえますね。