The Lullaby was developed by Bruce Banner between the events of Iron Man 3 and Avengers: Age of Ultron. Therefore Natasha has been using it for a maximum of 1.5 years, probably less.
After the events of Avengers: Assemble, Bruce Banner began working with Tony Stark & the other Avengers on ways to control his alter-ego. Foremost among these was the Veronica Protocol, which was
a space-based delivery system that launches the Hulkbuster armor along with its support module and vibranium cage.
It's safe to assume that, during this same period, Bruce worked with Natasha to develop a way of calming himself down when a mission was over. The Lullaby itself appears to be
a post-hypnotic suggestion method of causing The Hulk to revert to Bruce Banner. Natasha approaches Hulk using some variation of the phrase "The sun's getting real low." and then taps him at two locations on his arm.
Although we don't see the development of the Lullaby occur in any off-screen materials, a method like this would take several months to develop and test before it could be used in the field. Whereas Bruce would not want to try it without extensive testing, it's possible that Natasha could have tried it successfully on a mission without his prior approval.
The Battle of New York (Avengers: Assemble) occurred on May 4th, 2012. The raid on Baron von Strucker's base in Sokovia (Age of Ultron) occurred on April 29th, 2015. And we know that Bruce & Tony were working together as early as January 6th, 2013 (the therapy session seen in Iron Man 3). Therefore we have a window of almost two years between the two movies. Assuming at least six months development time to develop the Lullaby, we can deduce that Natasha has been using it in the field less than 1.5 years.