-- Made this video with instructions.
I tried tons of apps for connecting to wifi through my phone(tethering), but all of them used ad-hoc mode which the fire does not support.
My phone is the LG Esteem and I have 4G.
Finally after trying over 6 different apps, I went here:
Downloads - android-wifi-tether - Wireless Tether for Root Users - Google Project Hosting
Had to use the wifi_tether_v3_1-pre101.apk which is still a version in progress(beta).
Then in settings it says "Change Device-Profile" I clicked that and chose "LG Optimus S" as my phone. Yea I know I have LG esteem but it is not listed.
Once i did this, I clicked "press to start tethering" on my phone and my kindle fire can now connect with 4G speed through my LG esteem.
So, the officially released version of android tether does not have this option to choose phone type, so you need to try a beta or experimental version of this program such as the one I listed above in this post.
Now I can connect anywhere, anytime.