- A long-stay visa. You're on your own for this one.
- An Alien Registration Card. The only way to get one of these is to get some sort of long-stay visa.
- A Korean-issued credit card. Get this after you get the Alien Registration Card. Since you have no credit rating in Korea, you will also need to open a Korean bank account as collateral. You can do this with a passport when you arrive, or with your Alien Registration Card later on.
- A Korean citizen. Not for keeps - you can return them after signing up your phone.
- A Nexus One.
Then simply go to the KT Service Center and have your Korean friend tell them you want to register your American-bought Nexus One on KT's network. Two hours later, they'll sell you a sim card for 5500 KRW (about $5), charge like a $30 registration fee, and you're good to go. Better than spending $600 for a new one.
The main point of this is that now you have maps with GPS. See http://thedarren.blogspot.com/2010/11/address-systems-are-broken-in-korea-and.html.