how to get the n-th record of a datastore query
There is no efficient way to do this - in any DBMS. In every case, you have to at least read sequentially through the index records until you find the nth one, then look up the corresponding data record. This is more or less what fetch(count, offset) does in GAE, with the additional limitation of 1000 records.
A better approach to this is to keep a 'bookmark', consisting of the value of the field you're ordering on for the last entity you retrieved, and the entity's key. Then, when you want to continue from where you left off, you can add the field's value as the lower bound of an inequality query, and skip records until you match or exceed the last one you saw.
If you want to provide 'friendly' page offsets to users, what you can do is to use memcache to store an association between a start offset and a bookmark (order_property, key) tuple. When you generate a page, insert or update the bookmark for the entity following the last one. When you fetch a page, use the bookmark if it exists, or generate it the hard way, by doing queries with offsets - potentially multiple queries if the offset is high enough.
Suppose that I have the model Foo in GAE and this query:
query = Foo.all().order('-key')
I want to get the n-th record. What is the most efficient way to achieve that? 
Will the solution break if the ordering property is not unique, such as the one below:
query = Foo.all().order('-color')
edit: n > 1000
edit 2: I want to develop a friendly paging mechanism that shows pages available (such as Page 1, Page 2, ... Page 185) and requires a "?page=x" in the query string, instead of a "?bookmark=XXX". When page = x, the query is to fetch the records beginning from the first record of that page.