I read In God's Path: The Arab Conquests and the Creation of an Islamic Empire by Robert Hoyland a few years ago and he ends with the Abbasid Revolution. One of the letters he quoted is an Umayyad governor complaining about people converting leaving him without money to pay his garrison (I think, at least, my memory is a bit foggy on exactly what it was). But the argument Hoyland was making was that the Umayyads needed to continue taxing converts because their expenditures were calibrated to tax revenues prior to the population converting.
So that makes me wonder how the Abbasids afforded to run their empire if they abolished taxes on converts without having instituted anything new, so I presume they did have some newer forms of taxation, but I don't know so I'm asking here!
The Abbasid fiscal system and the Umayyad fiscal system were different. Under the Umayyads, taxes were collected from non-Muslims by their own notables, the Umayyads didn't really care how exactly you got money, they solely interested in the sum agreed upon. This created a problem when non-Muslims started to convert to Islam, escaping the juridiction of their non-Muslim notables and therefore shrinking their fiscal bases and so their ability to pay the required sums to the Arab governors.
Wellhausen details how the Rashidun to Umayyad fiscal system evolved (note that due to the paucity of documentation, this remains largely theoretical and not very clear). At the beginning of the conquests, one fifth of the loot went to the State and the land acquired through treaty paid tribute to the Caliphate, whereas those acquired by conquest were divided among the conquerors. Soon enough, once the loot stopped flowing, 'Umar ibn al Khattab proceeded to rearrange the fiscal system while keeping the Golden Rule: Arabs (the conquerors) don't pay taxes. From his era all acquired lands were under State administration and soldiers and their families' received stipends from the state.
This started to change when non-Arabs converted to Islam or sold their lands to the Arabs (who as you remember, didn't pay taxes) and the result was a significant shrinking of state's revenues. In The First dynasty of Islam, Gerald Hawting's explains that while both poll-taxes (the future Jizya) and land-tax (the future Kharaj) existed, it was the land-tax which was crucial to the state. He also explains that the true problem for the state was the abandonment of lands by tax-payers to go into the Amsar. This is because tax-collectors either made it hard to convert to Islam or ignored such conversion when they collected tributes. Land abandonment caused both a shrinking in tax revenue and a deterioration of lands because no one farms them.
Against this the governor of Iraq, Hajjaj Ibn Yussuf, expulsed the converts from the Amsar, the garrison cities peopled by the Arabs. But the problem was that it was not religiously acceptable because taxing Muslims was still unlawful.
The solution came under Umar ibn Abdel Aziz. As I said, the land-tax was the main source of revenue for the State, so his measures aimed at protecting them. He forbade Arabs from buying already Kharaj land and order that upon conversion, the lands would be given to the community (understand: the state) and if he chose to work it more, he was considered to be leasing and so he had to pay the land-tax because the land didn't belong technically to a Muslim.
As land-tax was the important source of revenue, he could easily do without the poll-tax which he "relieved" from non-Arab Muslims. In reality, the measure was never universally applied, but its principle was never forgotten. When the Abbassids gained power, they erased that technical loophole and just said that land-tax (kharaj now) was to be paid by everyone while imposing poll-tax only on non-Muslims (jizya now).