The last days I looked around for some great tools to do user interface prototyping for Android. I found two nice tools which work on Linux and other software platforms.
Pencil runs inside Firefox or as standalone version and allows to use different libraries and external images. The default version contains a few image libraries to prototype desktop applications. So you only need to download some user interface elements for Android as PNG or JPG an drop them easily via drag and drop into Pencil.
For the guys and girls who like to draw on real paper uistencils.com provide different stencils kits. You should definitely take a look at this website. Because wireframe templates can be downloaded for free.