Client - server integration testing: mock or not?

In your scenario you should continue to write unit tests to test individual classes, and integration tests to test the inter-operation between multiple application layers (e.g. business and database layers).

You ask:

"How to make true integration tests without sacrificing flexibility of independent tests"

All of your code should should use abstractions, so that you can use dependency injection to unit test classes in complete isolation using mock dependencies. The use of mocks will ensure that these tests will remain independent i.e. not coupled to any other classes. Hence taking this approach, the integration tests, which would use your final concrete classes, would not affect the unit tests which use the mocked classes.

Also:

"Should I test client with mocked server or with a real instance of my rest service?"

In addition to unit and integration tests you should also perform client-server integration testing; I use automated acceptance testing for doing this. Using a test framework such as Cucumber (also check out calabash-android, which is written specifically to test mobile applications) you can write tests which would test specific features and scenarios which would interact with both the client (your Android application) and server (your RESTful service). These client-server integration tests would start-up and stop concrete instances of the client and server.

Mocks are for unit testing. Your description of the tests with the mocks describes exactly that. You test the client and server as separate units.

Integration testing tests if the units work well together. Since the interface is a REST interface, mocking makes no sense then, you have to test the real thing over HTTP.

See also What is the difference between integration and unit tests?