So you are one hundred percent sure that there was a verbal agreement, and that your boss intends to be in breach of your verbal agreement. A verbal agreement is a legal contract that he is not allowed to breach - which is what should determine your attitude to things. It's also a legal contract which you can't prove - which is what should determine what legal actions you take.
Since your boss is in breach of a legal agreement, we are all in total agreement that you owe him absolutely zero loyalty, you owe him nothing. So first you start looking for alternative job; if you find one and sign a decent contract, you can tell your boss that you are leaving. Your notice is what is contractually required, which in the USA or elsewhere during your probabition period may be zero. The bigger mess you leave him in, the better.
If you are confident of finding another job, and confident in your job, you can talk to your boss, remind him of his promises, and tell him that you expect these promises to be kept. Don't argue about it, just put him on notice that you strongly disagree with his behaviour.