Would it be possible to get a spoiler warning?

So, I'm going to take this piece by piece. You might not have been looking for all this information, but here goes!

tl;dr: Before 1886, if Presidential office was vacant, VP would take over. VP would not be replaced. President Pro-Tempore of the Senate and then Speaker of the House were next in line. After 1886 (and until 1947), the same would happen, except if VP and President were incapable, the Cabinet Departments took over (in order of Department creation). After 1947, the same was true, except it went Speaker of the House, President Pro-Tempore, then Cabinet. Not until 1967, with the 25th Amendment, did there become a procedure for replacing a VP (President nominates, Congress confirms). There were never special elections. /end tl;dr

The original Constitution provided for a basic order of succession. You can view it by clicking here. Any areas that are links are things that were amended or changed. I'll get to that later. Moving to your first question:

In 1868, the House of Representatives impeached President Andrew Johnson; however, the Senate did not remove him from office. If the Senate had removed him from office, what would have been the line of succession to the president?

We actually have a precedent for this, amazingly (sorry, I get excited by politics, I'm a political science major :) )! In 1841, President Harrison died about a month into his presidency. This was unprecedented, and Harrison was the first president to die in office. The Constitution, as I linked above, provided for succession in Article 2, Section I. To quote the section:

In Case of the Removal of the President from Office, or of his Death, Resignation, or Inability to discharge the Powers and Duties of the said Office, the Same shall devolve on the Vice President, and the Congress may by Law provide for the Case of Removal, Death, Resignation or Inability, both of the President and Vice President, declaring what Officer shall then act as President, and such Officer shall act accordingly, until the Disability be removed, or a President shall be elected.

Basically, this means we knew from the beginning (when the Constitution was first written) that we wanted the Vice President to succeed the President. However, as with most of the Constitution, it was left pretty vague. Congress had passed a Presidential Succession Act, which lasted until 1886 (so it would've applied to Johnson, if he were impeached, and did apply to Harrison's case). As the Constitution says, the Vice President was to assume the President's position, and if there was no Vice President (as with the resignation of Nixon in the 1970s), then Congress was expected to have made or to make a law that would place someone in the presidential seat.

The Presidential Succession Act of 1792 said that, in the case of both the President and VP slots being vacant, the President Pro Tempore (PPT) of the Senate would replace the President, and the Speaker of the House (SotH) after the PPT. As was stated here:

Section 9. And be it further enacted, That in case of removal, death, resignation or inability both of the President and Vice President of the United States, the President of the Senate pro tempore, and in case there shall be no President of the Senate, then the Speaker of the House of Representatives, for the time being shall act as President of the United States until the disability be removed or a President shall be elected.

Source: http://www.amendment25.com/1792.html

In Section 10, it talks about how electors will be gathered and appointed to elect a new president if both President and VP were vacant, but until then the other two positions (PPT and SotH, whichever was necessary) would act as President.

In the case of Harrison, who died in 1841, there was a lot of confusion. Were there supposed to be special elections, held in emergency? Was Tyler (his Vice President) supposed to act as President for the time being? Was he acting president, or full president?

Eventually, they settled on him being named full President following a renewal of his oaths, if I remember correctly. Tyler became president, and served out the rest of what would've been Harrison's term. This would've been the same in the case of Andrew Johnson, as the precedent was already set.

As for Vice President, Tyler did not have one. There was nothing to decide who would be the new VP, and it seems they never did anything about it.

The Presidential Succession Act of 1792 was replaced in 1886, by a similarly named bill. This bill changed the order of succession. While the VP still took over for the President, in the event neither was able, Cabinet positions were placed next in line (in order of the Department's creation). This was State, Treasury, War, Attorney General, Post-Master General, Navy, and lastly Interior. However, there was still no word on what to do when a VP was elevated to President. We have only two examples of what happened under this section of US history, which are the Harding case (1923) and the Roosevelt Case (FDR in 1945).

President Harding was succeeded by Vice President Coolidge, who proceeded to run again in 1924. He could've, in theory, run again in 1928, but chose not to. Anyways, back to the point: Coolidge did get a Vice President, but only after winning election in 1924. Coolidge had no VP following the death of Harrison and his assumption of the presidency.

Now, I do want to point out that this was a common thing. When the VP died or resigned, he was not typically replaced. There were at least 13 vacancies by the time Coolidge was moved up to President, following the death of Harding.

In 1945, FDR died. Truman ascended to President near the start of what would've been FDR's fourth term, and had no vice president for the entirety of his term.

In 1947, Truman pushed heavily for a change to the Presidential Succession Act, and got what he wanted (in terms of a change, not sure if he wanted that specific change). It is the current presidential succession sequence used today. In short, it goes back to the 1792 guidelines, but places the Speaker of the House before the President Pro Tempore, then it goes into the Departments (in different order). So now it goes: VP, Speaker, Pro-Temp, Secretary of State, Treasury, Defense Attorney General, etc. (long list!). That, by the way, is what happens when the President resigns from office, and if the VP is gone too.

We had a situation similar to this back with Nixon. His VP, Spiro Agnew, resigned in 1973, in the first year of Nixon's second term. However, fortunately for us, there was finally something put in place that allowed for changes to the VP slot if it went empty! The 25th Amendment, passed in 1967, said this:

Section 2—Whenever there is a vacancy in the office of the Vice President, the President shall nominate a Vice President who shall take office upon confirmation by a majority vote of both Houses of Congress.

Source: http://www.britannica.com/EBchecked/topic/610993/Twenty-fifth-Amendment

So unless the President's life and VP's life end at the same time, or both become incapacitated (as happened in that really bad movie, Olympus Has Fallen), the President can nominate a new VP who has to be confirmed by both houses of Congress (similar to appointing a Cabinet position, only both houses vote instead of only the Senate). This was the first time a VP was appointed through the 25th Amendment, and when Nixon resigned in 1974, Ford assumed office (because he was Vice-President, and that's what happens!). He was, by the way, the first President to not have been elected as either VP or President. That had never happened before. People had won the Presidency without getting a majority of the electoral or popular votes (ie. John Quincy Adams), but this was the first time a President didn't even have to run for office in a popular election!