An 1860 New York Times article on the subject, which seems surprisingly relevant today, notes multiple occasions (specifically, in 1849 and 1855-56) on which, after several ballots where no candidate reached a majority, the standard was changed to a plurality of votes cast in the presence of a quorum.
A more recent Vox article indicates there hasn't been much in the way of updates since then. Votes can take months and this history is the precedent we have for resolving a deadlock.
In 1940, when a Speaker died during session, the House elected a new one by passage of a resolution.
Deschler's Precedents, Volume 1, Chapter 1 (Assembly of Congress), A (Meeting and Organization), § 6 (Election of the Speaker), available from the U.S. Government Printing Office here.
At the time period most relevant to this question and answer, the "mechanism to solve a deadlock" is that John Boehner will stay on until somebody else is identified who would win a majority of votes for the speakership.