Depends on why the pay freeze and hiring freeze has been put in place. Based on my experience with such situation, if a freeze has been put, there is nothing which can change the status quo, including going to HR. On top of it, the promise was verbal, you have nothing in writing. So its basically not enforceable. Going to HR may worsen your situation in this case.
My suggestion to you would be to discuss your situation with your boss and director, tell them your expectations at the same time, keep doing a good job and have some patience. There could be valid reasons for a pay freeze/ job freeze which you are not aware of. You need to assess if this is temporary and likely to lift next year or not. A frank discussion with your boss may help.
You could try and negotiate a grade and title change without salary change. While this may not make a lot of sense at first, each grade has a specific salary range. With change in grade, you will be at lower end of the salary range of the grade. Whenever pay freeze is lifted, you are likely to get a fat pay rise.
If you are willing to stick to the organization for some time, chances are organization will correct the anomaly in your pay and grade ( provided you are a good performer, and you smartly document this). It may not be able to meet it immediately due to business environment. Please discuss and document the decision this time. This way, if the director changes again, or you boss is changed, you would have proof. A simple way of documenting this could be to have a formal meeting with your director and then publish the minutes of meeting. Another way could be to bring it in your performance appraisal and then document the notes in a email to your boss.
If your boss/ director promises to resolve the situation asap, ask if they will be willing to put HR in loop of this , so that you don't loose out next year.
Lastly, if you feel that the organization is not going to promote you no matter what, or if you don't want to wait that long, its best to look out for a higher grade outside. Since you are already playing the role, it should not be too difficult to convince the new employer that you are a fit for the higher role. Try and assess if the organization is growing or not. If its not growing/ there are management challenges or any other signs that the situation is not temporary, its best to move outside and have a career with some other organization.