I've been doing Android dev for about 5 years, and I always just considered this a fact of life. I've worked on huge desktop applications where you'd have to run a build script that would take up to 30 minutes just to compile and run (we'd refactor it back down to 5 minutes, and it would creep back up to 30 over time). You'd get your compile time feedback for things like syntax on the module you were building, but to see your work integrated into the larger product, you just had to wait.
That said, this is also what unit tests can help with. I sometimes write unit tests not for the sake of testing, but for trying out code quicker than if I integrate it into the UI and wait for the build/deploy/run cycle. I do this for web service calls, parsing, validation, business logic, etc. For UI stuff, I don't believe there's a better answer than what you're already doing.