What do you want?

• If you just want to check for a connection to any network – not caring if internet is available – then most of the answers here (including the accepted), implementing isConnectedOrConnecting() will work well.
• If you want to know if you have an internet connection (as the question title indicates) please read on

Ping for the main name servers

public boolean isOnline() {
    Runtime runtime = Runtime.getRuntime();
    try {
       Process ipProcess = runtime.exec("/system/bin/ping -c 1 8.8.8.8");
        int     exitValue = ipProcess.waitFor();
        return (exitValue == 0);
    } catch (IOException e)          { e.printStackTrace(); } 
      catch (InterruptedException e) { e.printStackTrace(); }
    return false;
}

That’s it! Yes that short, yes it is fast, no it does not need to run in background, no you don’t need root privileges.

Possible Questions

• Is this really fast enough?Yes, very fast!
• Is there really no reliable way to check if internet is available, other than testing something on the internet?Not as far as I know, but let me know, and I will edit my answer.
• Couldn’t I just ping my own page, which I want to request anyways?Sure! You could even check both, if you want to differentiate between “internet connection available” and your own servers beeing reachable
• What if the DNS is down?Google DNS (e.g. 8.8.8.8) is the largest public DNS service in the world. As of 2013 it serves 130 billion requests a day. Let ‘s just say, your app not responding would probably not be the talk of the day.
• Which permissions are required?

  <uses-permission android:name="android.permission.INTERNET" />

  Just internet access – what surprise ^^ (BTW have you ever thought about, how some of the methods suggested here could even have a remote glue about the availability of internet, without this permission?)