There's two ways that I got it to work, a method KaleoOmega suggested (which he/she will post later) and another way. This method works with a rooted android on 4.2.2 (with SuperSu):
1. Download WifiTether 3.4
here
2. Change your SSID to 'attwifi'
3. Check MAC address spoof and enter a MAC address available
here
4. Enable data connection on your phone and start tethering.
5. It should attach to your 3DS and the magical green light of glory will flash.
6. Let the guilt of manipulating the awesome relay feature sink in.