Should I write a thank you note to a professor for his recommendation letter even if I didn't get the scholarship?
Absolutely. He probably feels bad that you weren't selected. Not as bad as you, of course, but he will want to know that you are ok in spite of a setback. Moreover he may be in a position to help you in future so you will want to make sure you keep lines of communication open. 

Beyond that, however, a professor who thinks enough of you to write the letter in the first place, probably is the sort of person who wants to be kept in the loop as your career progresses. He will greatly appreciate your thanks, I assure you. 

I once had a mentor in grad school. He was not my advisor, but I always used him as an example of a great professor, just as you describe your professor. 

Many years after I graduated I had occasion to revisit the campus, where he was still teaching (Dept Chair, I think). I told him how much is model of a professor and his mentoring meant to me, not only at the time, but over the intervening years. He thanked me and also said that professors don't hear such thanks very often. That saddened but also surprised me. He died not long after that, so I've been happy that I was able to express that to him in time. 

As for the words to use. Thanks is enough, but fill him in on your current plans and what has happened to you since you were last his student. Wish him well.