For this particular challenge, what are some of the factors that we will need to take into account?
1. Learning Theology, probably via The Oracle
2. Spreading the Apostolic Palace Religion to each of the AIs
3. Actually building The Apostolic Palace
4. Sufficiently pleasing at least 1 AI to act as a Voting Buddy
5. Having less than a certain percentage of the total Apostolic Palace votes ourselves, but getting more than said percentage when counting the Voting Buddy's votes (I think that the number is 75%, but please confirm for me or correct me)
For Theology, we need Monotheism and Writing. Assuming that we will build The Oracle, we also need Priesthood. There shouldn't be any real competition for The Oracle, so a start with Marble probably won't be necessary, especially since The Apostolic Palace doesn't need Marble.
Getting Writing allows for Opening Borders with most or all AIs, which means that we can probably get +1 Diplo Attitude after 25 turns of continuous Open Borders (although we might incur negative Diplo Attitude for Opening Borders with an AI's Worst Enemy and then refusing to cancel said Open Borders trade).
Bronze Working and Mathematics would also be of help for Chopping out The Apostolic Palace, while Alphabet would be of help to get +4 Fair and Forthright Trading Relations Diplo Attitude bonuses (although possibly also -4 You Traded with our Worst Enemies Diplo Attitude penalties if we are not careful to whom we gift techs).
Theoretically, we could rely on auto-spreading of the Apostolic Palace Religion, but in all likelihood, it will be faster to move Missionaries across of the map than to build Roads and wait for random spreading, since random spreading requires a Trade Network connection. So, it might make sense to stick with the minimum number of AIs required (four), to reduce the number of Missionaries needed.
Since we'll be founding multiple Religions (Hinduism, Judaism, and Christianity at a minimum, and possibly Buddhism if we want the AIs to be united amongst each other for no Worst Enemies), we'll probably want to consider spreading the chosen Apostolic Palace Religion to at least a second City of ours, to allow for 2 Missionaries to be made simultaneously when making Missionaries for the AIs and to also give us a couple of more votes, to reduce the number of AIs who will have to vote for us.
Since it's Settler Difficulty, I believe that most AIs like us by an automatic +2 or +3 Diplo Attitude without even having to do anything, so we shouldn't need Favourite Civic bonuses to get at least one Voting Buddy.
By building The Apostolic Palace ourselves, even if we aren't the highest in population points for The Apostolic Palace's Religion, we'll be a candidate for the AP Resident position, which is a position for which we'll want to be elected, in order to call the Religious Victory vote, instead of relying on an AI to randomly select that AP Resolution.
By liberally gifting techs, we'll also likely easily be elected as the AP Resident and it shouldn't be too hard to get enough of the AIs to like us in order to vote for us to win on the first AP Leader Resolution.
So, the toughest part of this challenge will be to balance the completion of all of those tasks. Playing through a couple of games will probably be a good way to figure out which factors are the bottlenecks, so that we can focus on trying to speed up the completion of the factors which end up slowing down the victory date the most.