1981
Snape states in Order of the Phoenix that he has been a teacher at Hogwarts for fourteen years.
"Now...how long have you been teaching at Hogwarts?" she asked, her quill poised over her clipboard.
"Fourteen years," Snape replied. His expression was unfathomable. His eyes on Snape, Harry added a few drops to his potion; it hissed menacingly and turned from turquoise to orange.
"You applied first for the Defence Against the Dark Arts post, I believe?" Professor Umbridge asked Snape.
"Yes," said Snape quietly.
"But you were not successful?"
"Obviously."
(Order of the Phoenix, Chapter 17, Educational Decree Number Twenty-Four).
Snape makes this comment in around October 1995, meaning that he must have begun teaching in 1981. Presumably he started teaching at the start of the school year, making his first day 1st September 1981.
Note that in the quote that Snape gives fourteen years is the length of time that he has been "teaching at Hogwarts". He gives no hint of any other, less senior posts. Neither indeed do we hear any mention of any trainee or junior teaching roles elsewhere. There are only teachers and non-teachers (like Madame Pomfrey and Filch). It seems that Snape applied for the DADA job, didn't get it and then subsequently was offered the role of Potions Master, which he took without any period of training or probation. Since he was a rare talent at Potions he was still an excellent candidate, even given his youth.
Rand al'Thor very sensibly points to Pottermore to demonstrate that Snape was born on 9th January 1960. We can verify this date of birth from the books because Lily and James, who were in the same school year as Snape, were also born in 1960.
JAMES POTTER
Born 27 March 1960, died 31 October 1981
LILY POTTER
Born 30 January 1960, died 31 October 1981
(Deathly Hallows, Chapter 16, Godric's Hollow).
Thus on 1st September 1981 Snape would have been 21 years old. Yes, this makes Snape a young teacher but he wasn't the only one. Minerva McGonagall was hired at basically the same age.
As for what Dumbledore can get away with, he can more-or-less appoint anyone he wants. Up until Educational Decree Number 22, anyway - and even then the Ministry could only hire someone if the Headmaster couldn't find a candidate.
As recently as 30th August, Educational Decree Number Twenty-two was passed, to ensure that, in the event of the current Headmaster being unable to provide a candidate for a teaching post, the Ministry should select an appropriate person.
(Order of the Phoenix, Chapter 15, The Hogwarts High Inquisitor).
Dumbledore isn't accountable to anyone, apart from perhaps the board of governors and the parents. Some people may very well have been unhappy with Dumbledore hiring an ex-Death Eater, and a very young one at that. Dumbledore is well used to putting up with this sort of criticism, however. He had a thick skin and tended to ignore the gripers.
"Really Hagrid, if you are holding out for universal popularity, I'm afraid you will be in this cabin for a very long time," said Dumbledore, now peering sternly over his half-moon spectacles. "Not a week has passed, since I became Headmaster of this school, when I haven't had at least one owl complaining about the way I run it. But what should I do? Barricade myself in my study and refuse to talk to anybody?"
(Goblet of Fire, Chapter 24, Rita Skeeter's Scoop).