Hooray! I just made the Personal Hotspot on my old iPhone 4 working by following the instructions in this Apple Community thread. Now I have internet in this place I am going to spend the next two weeks.
I am on Idea Cellular 3G and their customer care isn’t helpful in helping me setup Personal Hotspot. They made me go back and forth between their dongle and 3G support phone numbers. Each of the reps told me to contact the other. I clearly did not do a good job of explaining what a Personal Hotspot is.
Fed up, I googled for idea cellular personal hotspot in the phone and the first result is the aforementioned Apple Community thread. Except that in my iPhone 4 running iOS 7.1.2, I had to go to Settings > Mobile > Mobile Data Network. I then entered internet in the APN field under Mobile Data and Personal Hotspot sections. Username and Password fields can remain blank.