Androidで完璧なテザリングができるアプリはありますか？

テザリングがうんぬん以前に「3Gデータ通信」回線だと自由な通信ができません。
データの総量規制やポートの規制を行っている場合がほとんどです。

　今年の３月にタイで　ＧＡＬＡＸＹ　Ｙという安いスマホを買って現地ではＤＴＡＣというキャリアの１Ｇバイト使い切りの４Ｇ（世代）携帯ＳＩＭを買って使いました。
　それは設定に既にＴｅｔｈｒｉｎｇと設定する箇所が有り、ハードウェアで機能が付いています。
　ルーターと同じ様な設定をすれば親として使えます。ルーターになるスマホですね。
　上海ではＣｈｉｎａ　Ｕｎｉｃｏｍというキャリアの４Ｇの使い切りＳＩＭが使えました。
　それを日本では日本語化してＡＭＡＺＯＮで３１５０円？で買ったｅ－ｍｏｂｉｌｅの４Ｇ（世代）ＳＩＭ定額　５００Ｍバイトで一か月１９８０円で使っています。ＳＩＭはドコモのＬＴＥみたいです。
　通話は出来ませんが、家ではＷＩ－ＦＩの子として、外では親としてＰＣやガラケーやタブレットを子として使っています。動画なんかは家でＷＩ－ＦＩの子として使って見ていますのでキャリアは使いませんので５００Ｍバイト／月で十分です。５００Ｍ使い切ったら翌月までＷＩ－ＦＩのみですけど。
　電話はガラケーで２台持ちですが、ガラケ－もＷＩ－ＦＩで繋がりますので実質携帯スマホ通信費はどんなに使っても合計で４０００円／月もしません。ガラケーもスマホもタブレットも家ではＷＩ－ＦＩ接続ですので料金も非常に安いですね。
　ネットでＧａｌａｘｙ　Ｙが日本でも買えるみたいです。３Ｇ（世代）でＴｅｔｈｒｉｎｇは厳しいですよ。但し、日本語化を含めて設定等も自己責任でお願いしますね。私は仕事で現地で買わざるを得なかっただけなのでこうなっただけなのですので。
　日本でも最近のスマホには大体Ｔｅｔｈｒｉｎｇ機能が付いているみたいですね。それぞれの機種の機能を見れば”ＷＩ－ＦＩテザリング”機能が付いているかどうか分かります。
　日本のキャリアは少々維持費が掛かりますが。

最近って、IPv4のIPアドレスが不足しているから、端末には、プライベートIPを割り与えてるようになっています。
Proxyサーバを経由しているはずですから、それに遮断される場合もあります。

※グローバルIPが割り与えられるISPと契約して接続すれば、回避出来る可能性があります。
携帯電話キャリアが提供するISPサービスでは無理でしょう。
ただし、NTTドコモのmoperaUやKDDIのau-one（旧DION）は例外です。
NTTドコモのSPモードやKDDIのISNET（EZWIN）はプライベートIPとなります

回線上に問題がある場合は回避できません。