J.E. Lighter, Random House Historical Dictionary of American Slang (1997) has separate entries for noogie and tough noogies but includes first cites to each term from 1972—and specifically from New York University:
noogie {orig. unkn.} 1. Juve. an act of rubbing or striking a person's head with the knuckles, esp. as a penalty. Also as v. [First cited occurrence:] 1972 N.Y.U. student: A noogie is a kind of a punch or a jab you give someone with your third and middle finger. You do it on the forehead or the shoulder. 2. usu. pl. a testicle. Joc. [Cited occurrence:] 1985 Northport, N.Y., woman, age 33: It's better than freezing your noogies off.
In phrase:
tough noogies! hard luck! too bad! [First cited occurrence:] 1972 N.Y.U. student: Tough noogies! is something we used to say {*ca*1959} for tough shit!
All three of Lighter's first occurrence's are from New York, although the earliest instance of "tough noogies" that I found (from 1967) is from Washington, D.C. From Sherry Schultz, "Soiree: O, Heighdy Ho," in the [American University, Washington, D.C.] Eagle (April 14, 1967) includes this item:
TOUGH NOOGIES
Congratulations to Brother Dennis Apfel of ZBT on his engagement to Donna Londesman. It seems as if ZBT will have a few sisters next September. One final word to the ZBT pledges about Supremacy Day: Tough Noogies!!
This expression seems to have had some staying power, too, as it appears again in "Bulletin Board," in the [Ithaca, New York] Ithacan (April 1, 1977):
The Registrar would like to remind students that anyone considering applying for financial aid for next year should pick up an official form from the Registrar's Office on Job Hall Two no later than March 21, 1977. Applications after this date can not be considered. The Registrar would also like it known that financial aid is not available for professors. If they do not negotiate a higher salary for themselves at contract time, tough noogies.
An early instance of noogies in the sense of "testicles" appears in Thomas McGuane, The Sporting Club (1968):
People went to and fro as though in a blackout, with a rather useless air of carrying on. A portable generator ran somewhere and lightbulbs hung in the trees, swung and heaved in the breeze and threw monstrous shadows everywhere. The children were playing in the black rectangle of shadow at the end of the tent and their fierce voices came brokenly. ". . . no, you can't! . . . Eat it raw!" Then the piping voice of a little girl, "Okay for you, Billy! Now I have to kick you in the noogies!"
The word appears in a semi-nonsense form in an unidentified poem in Howard Rosenburg, Counterpoint: An Anthology of Modern Poetry (1966):
some of our nervous noogies and other / communismists will say sublusive / things like: / What, Ho!— / i thought it was their country / and we have no business over there— / but we'll issue press releases. / if the noogie element doesn't calm down / we'll / put all the nervous noogies in jail for / their protection. we'll call the jails / strategic hamburgers / there will be onions.
Unfortunately, I have not been able to find out anything about the author of this 1966 instance of the word, nor is the word at all well defined here.
Conclusion
We have instances of "tough noogies!" in the sense of "tough luck!" from 1967, of noogies in the sense of "knuckle jab" from 1968 (in the Israel Horovitz play, The Indian Wants the Bronx, cited in Hugo's answer), and noogies in the sense of "testicles" also from 1968, as well as the strange instance of noogies in an unclear, possibly idiosyncratic sense from 1966. The first occurrences occur in a chronological clump, despite having seemingly quite different meanings.
The connection to New York seems strong in most of these early instances, but the etymological puzzle remains as unclear as ever.