(Update: Mockito has added Android support as of version 1.9.5 and EasyMock has added Android support as of version 3.2 by factoring out those bits that generate code at runtime and making them pluggable, e.g. by using dexmaker instead of cglib.)
Except for android-mock mentioned by DixonD (which is a fairly young, unproven library), there currently is no solution. You can immediately forget anything based on CGLib (Mockito, plain EasyMock), since CGLib relies on byte code generation and won’t work on Dalvik (it also relies on the Java Beans package, which is also not part of Android).
For what it’s worth, you could use the very few mock classes coming with Android (like MockContext), but they don’t verify behavior, they’re just stubs. Their default behavior is to throw a runtime error in every method, so you have to subclass them and override the methods you want to mock.
However, you can still use mocking libraries in non-instrumentation tests, i.e. in your standard unit tests executed on the JVM. You can use PowerMock to mock framework methods, it has support for mocking static methods and constructors, making the mocking as powerful as e.g. in Ruby (just more painful to use).
We use JUnit 4 + PowerMock + Mockito and mock out classes like Context and TextUtils in a base class from which we inherit every normal JUnit test. For instrumentation tests, we create custom mock classes and decide using a factory which implementation (mock or not) to instantiate at runtime.