Christine Ammer, American Heritage Dictionary of Idioms (1997) confirms that "get off" in the sense you're referring to dates to the early 1900s:
get off ... 7. Have the effrontery to do or say something. For example, Where does he get off telling me what to do? [Colloquial; early 1900s]
I suspect that it is related to the expression "on one's high horse." Here is Ammer again, on that idiom:
on one's high horse In an arrogant or condescending manner. For example, When they started talking about music, David got on his high horse and said that classical music was only fit for museums and archives. This expression, alluding to the use of tall horses by high-ranking persons, dates from the late 1700s. Similarly, off one's high horse means "less arrogantly, more humbly," as in I wish she'd get off her high horse and be more friendly. It dates from the early 1900s, but is heard less often today.
According to Ammer, "get off" [meaning #7] and "get off one's high horse" arose at approximately the same time, raising the possibility that the former is a shortening of the latter.
Unfortunately for this theory, however, Chapman & Kipfer, Dictionary of American Slang, third edition (1995), dates "get off one's high horse" only to "by 1928"—a dog's lifetime after the 1913 occurrence of "where do you get off" that you point out. Here's the relevant entry in Chapman & Kipfer:
get off one's high horse v phr by 1928 To stop being haughty and superior; deal informally; =COME OFF one's PERCH [The notion of high horse, "pretentious arrogance," is found by 1716]
On the other hand, that same source states that "get on one's high horse" was current "by 1856," so perhaps people were addressing the question "where do you get off?" to someone who was on his or her high horse, long before they thought to speak of the person afterward as being "off his/her high horse."
First Occurrences of the Phrase as a Rhetorical Challenge
The Random House Historical Dictionary of American Slang (1994) finds an occurrence of the phrase in George Ade, "The Fable of the Regular Customer and the Copperlined Entertainer," in More Fables (1900). Here is the full paragraph where that instance occurs:
Mr. Byrd's first Move was to take Jim to a Retreat that was full of Statuary and Paintings. It was owned by a gray-haired Beau named Bob, who was a Ringer for a United States Senator, all except the White Coat. Bob wanted to show them a new Tall One called the Mamie Taylor, and after they had Sampled a Couple Jim said it was all right and he believed he would take one. Then he told Bob how much he had taken in the Year before and what his Fixtures cost him, and if anybody didn't think he was Good they could look him up in Bradstreet or Dun, that was all. He said he was a Gentleman, and that no Cheap Skate in a Plug Hat could tell him where to Get Off. This last Remark was intended for an inoffensive Person who had slipped in to get a Rhine Wine and Seltzer, and was pronging about Forty Cents' Worth of Lunch.
Ade returns to the expression "The Fable of the Crafty Love-Maker who Needed a Lady Manager," in The Girl Proposition (1902):
He wore his Chest a few Inches in front of himself and no one could tell him where to get off. Inasmuch as he was a big, husky Good-Looker with all the Manly Accomplishments, he had a Panel Picture of himself leading Miss Blonde into a Flat.
Rosemarie Ostler, Let's Talk Turkey: The Stories Behind America's Favorite Expressions has a fairly lengthy but ultimately inconclusive discussion of "tell someone where to get off," as well.
One of the first occurrences of the challenging question "Where do you get off?" occurs in Alfred Lewis, "The Diary of a New York Policeman," in McClure's Magazine (January 1913):
As a starter I made a meet with Baden. He was rough and high, as I knew he would be. After letting him bullyrag me to his soul's content, I started to leave with—apparently—my tail between my legs.
"Where do you get off," he roared after me—it was perhaps his mildest utterance—"to go givin' me a talk? If you and Muggs go to monkeyin' with me, you'll get it where the baby wore the beads."
An even earlier instance appears in the lyrics to "Personality" "as sung by Eva Tanguay" in The Philistine (March 1911):
Ev'ry time I come to town, the knockers get their hammer,
And they call me pretty names like "Faker" and "Flim-flammer."
Some of them will tell you that I'd rather fight than eat—
Also that, for raising Cain, I've got old Satan beat ;
Actors on the bill say: "Mercy I where does she get off?
On the level, Cull, how does she make them wise guys cough?"
Hark to little Eva, and a tale I'll tell to thee—
Some one wished it on me—why, personality.
An Alternative Origin Theory
Most people who have discussed the two phrases have supposed that the phrase "tell [someone] where to get off" and the question "where does [someone] get off" have a common origin. But Google Books search results suggest the possibility that while the declarative "tell [someone] where to get off" makes sense in the context of a streetcar conductor, the earliest instances of the question "where does [someone] get off" may have an independent origin.
Specifically, the first match for "where does he get off" occurs eleven years before George Ade's first use of the declarative form, and it arises in a peculiar context: a hearing in the California Senate in about hay prices. I'll quote the example at length because the usage is so clearly idiomatic. From Appendix to the Journals of the Senate and Assembly of the Twenty-Eighth Session of the Legislature of the State of California, volume 8 (1889):
MR. HOOK: Was it a necessity of having this ground plowed up by the people that had leased it? A. Was it a necessity?
Yes? A. I look upon it as a necessity to raise all the hay that a man can get.
Q. In the valley? A. Yes, sir; it is impossible almost to get hay in the valley at a reasonable price, and unless there is some hay raised in the valley to regulate the price, there is no telling where you would get off. In 1875 and 1876 I didn't get a ton of hay in the valley for less than $60 a ton, and it came down to $55 and $50; and year before last I didn't buy any hay that I didn't pay $47 50 for, and then couldn't get really enough to do me. I got two bales at a time, and had to turn out some carriage horses to grass. If you take ninety or one hundred head of horses in there, and keep them for seven months, you can figure how much hay it will take; and I undertake to say that right here that it is impossible to get that amount of hay from outside; and you stop raising a little hay in the valley to govern the price, to make a little stand-off with them, and the farmers on the outside, knowing that that hay has to be used, they will pool it as well as any others, railroads or any others, and say, "Here, you can't have our hay for less than $55 or $60 a ton," and I should have to pay it. Now hay forty-five miles—that is, where you have to haul it—forty-five miles from the valley, will sell at home for $20. They don't make anything by hauling that hay and selling it for $45. Hat forty-five miles from the valley is worth $20. Ten months in the year it is worth $20. A four-horse team can't haul but a ton, and a six-horse team will haul a ton and a half, it takes him a week to make the trip—six days—he pays toll over and back. His hay is worth $30 at home—a ton and a half—and when he gets into the valley, where does he get off, after paying freight and expenses? You can see, yourself, that it would be impossible to get it at any price. They don't raise, even then, at the price they would put it at, there is not enough raised within forty-five miles to do the business.
In this excerpt, "where you would get off" seems to mean something like "how you would make [an arrangement] work financially," "how would you get out from under [onerous contract terms]," or simply "how you would benefit [from an arrangement]."The connection to a high horse simply isn't there, and the connection to a railway conductor is remote at best.
This is by no means the only example where "where does one get off" has this distinctive meaning. For instance, from "Prevention of Dealing in Futures," in U.S. Congress, Hearings Before the House Committee on Agriculture, volume 2 (1910), we have this:
Mr. FITCH. Mr. Chairman, I want to say just one word in connection with that term "bucket shop." And in illustration of that, Mr. Chairman, I desire to go back again to Springfield, Ill., to John Smith who is in the grain business. I explained to you how that 10,000 bushels of corn for May delivery ere sold upon the Chicago Exchange; that John Smith was notified to whom it was sold, and the firm who bought it notified the party from whom they bought it, and so forth, making it an actual transaction. I want to show you where those methods differ from what they would have been if John Smith had stepped across the street to one of the small town bucket shops. If he had gone across the street to a bucket shop to make that sale of corn, the method would have been to look at the quotations on the board,the blackboard that these men keep there, and he writes him a ticket at the price, and the transaction ends right there. It would be just the same as if I were to go behind the stand at the race track and lay them 5 to 0 or 5 to 2, and so forth—identically the same proposition.
Now, you may say that if the bucket shop takes these bets, as you call them, where does he get off if the market goes against him? I would say to you that once in a while he finds somebody that is a member of the exchange who will handle some of his business. The member will do it for him under cover and give him a chance to get off, but if a member does it and is found out he never does it the second time; he is expelled.
And from J.E. Rhodes, "An Appeal to Yellow Pine Lumbermen," in Lumber World Review (May 10, 1915):
"WHERE DO YOU GET OFF?"
And, Mr. Timber Owner and Lumber Manufacturer, where do you get off?
You are now facing the absolute necessity of exerting your utmost efforts to restore the lumber industry to what it can easily be, or you will not realize upon your investments anything like the returns that you had anticipated.
And from a letter by M.J. Whittall dated January 27, 1917, to the U.S. House Committee on Interstate and Foreign Commerce, reprinted in Hearings Before the Committee on Interstate and Foreign Commerce of the House of Representatives (1917):
Now, what about the small dealer, not only in New York City but for miles around, where New York City papers are read. Some of these dealers have only floor coverings ; others only floor coverings and furniture. Where do they get off if Mr. Straus succeeds in proving that 15 per cent is a reasonable profit and that everyone should do all their shopping at Macy's?
And from Hugh Kennedy, "Delbart: Timber Cruiser," in Saturday Evening Post (1919):
"I considered it [namely, warning that "they may want to ask you some questions at the other end"] was the least I could do. Purser Tenney, he's a good little man in the main. Bit of an old woman, perhaps, and a little irritable lately; needs a holiday, I should say. It's family trouble, I guess. In this business there's been no reasoning with him."
"Lost his nerve, eh? If they push this thing where does he get off?"
"That's just it! He's under heavy bonds on account of this monthly pay roll. It may go hard with him. He'll lose his job at the least.You can't altogether blame him for being in such a funk. Damned nuisance, I call it, all round!'
And from P.G. Wodehouse, "Aunt Agatha Makes a Bloomer, in Cosmopolitan (October 1922):
"I must say Aunt Agatha, dash it all," I said severely, "I think you have been infernally careless. There's a printed notice in every bedroom in this place saying that there's a safe in the manager's office where jewelry and valuables ought to be placed and you absolutely disregarded it. And what's the result? The first thief who came along simply walked into your room and pinched your perls. And instead of admitting that it was all your fault, you started biting this poor man here in the gizzard. You have been very, very unjust to this poor man."
"Yes, yes," chipped in the poor man.
"And this unfortunate girl, what about her? Where does she get off? You've accused her of stealing the things on absolutely no evidence. I think she would be jolly well advised to bring an action for—for whatever it is and soak you for substantial damages."
Though usage of "where does one get off?" in the sense of what are one's pecuniary self-interest shows up in Google Books search results 22 years before the same question shows up as (arguably) a rhetorical question about someone's gall or nerve, both meanings coexisted for at least a couple of decades after that, before that rhetorical question eventually won out. It's hard to say whether the rhetorical question arose out of the pecuniary self-interest question, but I wouldn't be shocked if it had. Another possibility is that both meanings arose out of some yet earlier ancestor.
In any event I would love to see a qualified historian of the language look into this hitherto underreported sense of "where does one get off?" from 1889.