SecurityException: Permission denied (missing INTERNET permission?)
NOTE: I wrote this answer in Jun 2013, so it's bit dated nowadays. Many things changed in Android platform since version 6 (Marshmallow, released late 2015), making the whole problem more/less obsolete. However I believe this post can still be worth reading as general problem analysis approach example.
Exception you are getting (SecurityException: Permission denied (missing INTERNET permission?)), clearly indicates that you are not allowed to do networking. That's pretty indisputable fact. But how can this happen? Usually it's either due to missing <uses-permission android:name="android.permission.INTERNET" /> entry in your AndroidManifest.xml file or, as internet permission is granted at installation not at run time, by long standing, missed bug in Android framework that causes your app to be successfully installed, but without expected permission grant.
My Manifest is correct, so how can this happen?
Theoretically, presence of uses-permission in Manifest perfectly fulfills the requirement and from developer standpoint is all that's needed to be done to be able to do networking. Moreover, since permissions are shown to the user during installation, the fact your app ended installed on user's device means s/he granted what you asked for (otherwise installation is cancelled), so assumption that if your code is executed then all requested permissions are granted is valid. And once granted, user cannot revoke the permission other way than uninstalling the app completely as standard Android framework (from AOSP) offers no such feature at the moment.
But things are getting more tricky if you also do not mind your app running on rooted devices too. There're tools available in Google Play your users can install to control permission granted to installed apps at run-time - for example: Permissions Denied and others. This can also be done with CyanogenMod, vendor brand (i.e. LG's) or other custom ROM, featuring various type of "privacy managers" or similar tools.
So if app is blocked either way, it's basically blocked intentionally by the user and if so, it is really more user problem in this case (or s/he do not understand what certain options/tools really do and what would be the consequences) than yours, because standard SDK (and most apps are written with that SDK in mind) simply does not behave that way. So I strongly doubt this problem occurs on "standard", non-rooted device with stock (or vendor like Samsung, HTC, Sony etc) ROM.
I do not want to crash...
Properly implemented permission management and/org blocking must deal with the fact that most apps may not be ready for the situation where access to certain features is both granted and not accessible at the same time, as this is kind of contradiction where app uses manifest to request access at install time. Access control done right should must make all things work as before, and still limit usability using techniques in scope of expected behavior of the feature. For example, when certain permission is granted (i.e. GPS, Internet access) such feature can be made available from the app/user perspective (i.e. you can turn GPS on. or try to connect), the altered implementation can provide no real data - i.e. GPS can always return no coordinates, like when you are indoor or have no satellite "fix". Internet access can be granted as before, but you can make no successful connection as there's no data coverage or routing. Such scenarios should be expected in normal usage as well, therefore it should be handled by the apps already. As this simply can happen during normal every day usage, any crash in such situation should be most likely be related to application bugs.
We lack too much information about the environment on which this problem occurs to diagnose problem w/o guessing, but as kind of solution, you may consider using setDefaultUncaughtExceptionHandler() to catch such unexpected exceptions in future and i.e. simply show user detailed information what permission your app needs instead of just crashing. Please note that using this will most likely conflict with tools like Crittercism, ACRA and others, so be careful if you use any of these.
Notes
Please be aware that android.permission.INTERNET is not the only networking related permission you may need to declare in manifest in attempt to successfully do networking. Having INTERNET permission granted simply allows applications to open network sockets (which is basically fundamental requirement to do any network data transfer). But in case your network stack/library would like to get information about networks as well, then you will also need android.permission.ACCESS_NETWORK_STATE in your Manifest (which is i.e. required by HttpUrlConnection client (see tutorial).
Addendum (2015-07-16)
Please note that Android 6 (aka Marshmallow) introduced completely new permission management mechanism called Runtime Permissions. It gives user more control on what permission are granted (also allows selective grant) or lets one revoke already granted permissions w/o need to app removal:
This [...] introduces a new permissions model, where users can now directly manage app permissions at runtime. This model gives users improved visibility and control over permissions, while streamlining the installation and auto-update processes for app developers. Users can grant or revoke permissions individually for installed apps.
However, the changes do not affect INTERNET or ACCESS_NETWORK_STATE permissions, which are considered "Normal" permissions. The user does not need to explicitly grant these permission.
See behavior changes description page for details and make sure your app will behave correctly on newer systems too. It's is especially important when your project set targetSdk to at least 23 as then you must support new permissions model (detailed documentation). If you are not ready, ensure you keep targetSdk to at most 22 as this ensures even new Android will use old permission system when your app is installed.
Android Studio 1.3b1 (not sure about other versions) autocompleted my internet permission to ANDROID.PERMISSION.INTERNET. Changing it to android.permission.INTERNET fixed the issue.
Be sure that the place where you adding
<uses-permission android:name="android.permission.INTERNET"/>
is right.
You should write it like that in AndroidManifest.xml :
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
package="com.project">
<uses-permission android:name="android.permission.INTERNET"/>
Dont make my mistakes :)