This answer primarily addresses the first question of the four asked above—"Was 'Whatever tickles your fancy' originally a double entendre expression?" It also looks (although not exhaustively) into the second question—"Where and when was it first used?" I have not attemptd to answer the third and fourth questions.
Early Google Books instances of 'tickle [one's] fancy'
I consider it unlikely that the phrase "tickle [one's] fancy" originated as a double entendre. One of the earliest matches for the phrase that a Google Books search finds is from The Princesse Cloria, or, The Royal Romance (1661), spoken by man named Creses:
No sooner was I come to the presence of Hercrombrotus, but according to his usual fashion of dissimulation, he received me with a most chearful countenance, (seldom putting on other to his greatest enemies) and withal discoursed with such loving and familiar language, as if that night I should have been his Bed-fellow, pretended onely out of affectionate confidence; which I must confess tickled my fancy, however it settled not my thoughts, since I knew not how to interpret all these alterations; especially in what concerned my Lord Arethusins affairs, appearing with a face so much now contrary to his own former professions:
There is no evident sexual implication here.
Four years later, from Francis Kirkman [Richard Head), The English Rogue: Continued in the Life of Meriton Latroon, and Other Extravagants, the Second Part (1665):
And because thou art as yet but a Novice in begging, and understand not the mysteries of the Canting language, to principle thee the better, thou shalt have a Doxy to be thy Companion, by whom thou maist receive fit instructions for thy purpose. And thereupon he singled me out a young Girl of about fourteen years of age, which tickled my fancy very much that I had gotten a young wanton to dally withal; but this was not all, I must presently be married unto her after their fashion by their Patrico, (who among Beggars is their Priest) which was done after this manner.
Here the setting is sufficiently heavy with sexual interest, but the context indicates that nothing licentious can yet have occurred—and in any case it is the boy, not the girl, whose fancy is tickled. In an odd way, the fact that this setting invites innuendo makes the lack of any evident double entendre here a stronger than usual point in favor of the argument that the phrase didn't have a widely recognized double meaning in 1665.
Another early instance presents an even less plausible occasion for double entendre. From William Allen, The Danger of Enthusiasm Discovered, in an Epistle to the Quakers (1674):
But doubtless the inward Pride, the over-valuing of your selves, which I have been admonishing you of, hath had a great hand in bringing you to it [a belief "That the Light within, without being taught by man or by the Scripture, is the Rule of Faith and Practice"]. And if ever you be recovered from this snare of the Devil, it must be by being brought to a sight and sence of your own injudiciousness and ignorance, and altogether groundless confidence. And if you were but well awakened out of that Spirit of Slumber, into which your intoxication hath cast you, and out of that pleasant Dream in it, which hath so tickled your fancy, you would be ashamed and confounded before God and Men, that ever you should be so strangely deluded, and prevailed upon as you have been, to trouble the World with your whimsies and fancies, and thereby to bring a scandal upon the Christian Religion, and make sport for them that have no mind seriously to consider the things of the Gospel, and to encourage Romish Agents in their design against the Reformation.
And from William Howel, An Institution of General History, Or the History of the Ecclesiastical Affairs of the World (1685):
No sooner had he [Peuda, of Mercia] got the Power into his Hands, but he improved it for the Molestation of his Neighbours, thinking it no fault at all to disturb the World, to ruine Families, overturn Kingdoms, and destroy a Multitude of innocent Souls, and all to gratify the humour of one single Man, to tickle his fancy with the pitifull thought of domineering; the true account of the 'Actions of Conquerours, (or as that little one told the greatest of them) those publick Pirates who rob with whole Armies and Fleets, whose Power makes their Murthers and Robberies lawfull, and alone distinguisheth them from those puny ones, to which the Halter is appropriate.
Early EEBO instances of 'tickle [one's] fancy' [New section, April 26, 2020]
Early English Books Online finds some additional early instances of "tickle [one's] fancy" that involve no evident double entendre. For example, from William Gurnall, The Christian in Compleat Armour. Or, A Treatise of the Saints War Against the Devil (1655):
The Sun is not more troublesome in hot Countreys, then truth is to those who sit under the powerful preaching of it; and therefore as those seldome come abroad in the heat of the day, and when they must, have their devices over their heads to skreene them from the Sun; so sinners shun as much as may be the preaching of the Word; but if they must go to keep in with their relations, or for other carnal advantages, they, if possible, will keep off the pow∣er of truth, either by sleeping the Sermon away, or prating it a∣way with any foolish imagination which Satan sends to beare them company and chat with them at such a time: or by choosing such a coole Preacher to sit under, whose toothlesse discourse shall rather flatter then trouble, rather tickle their fancy then prick their consciences; and then their sore eyes can look upon the light.
From Richard Baxter, The Vain Religion of the Formal Hypocrite (1660):
You like that teaching that sooths you in your own opinions, and galleth not your consciences in the guilty place: A Ministry you would have, that should stand like an adorned Idol that hurts no body, and toucheth not your sores: or that is but instead of a pair of Organs, or a tinckling Cymbal, to tickle your fancy, and make Church-worship to be as a kind of religious stage-play to you.
From a 1661 translation by Percy Enderbie of Benedictus Pererius, The Astrologer Anatomiz'd, or, The Vanity of Star-Gazing Art Discovered by Benedictus Pererius:
True, the vulgar who have ordinarily dull and gross intellects, apt to believe any thing which tickles their fancy; men credulous and itching to hear novelties, are much taken with these chymera's, and give confident belief to such fopperies, and many shallow and giddy brain'd fools are taken with this vanity, rather for lucre sake then truth.
From John Sergeant, A Letter of Thanks from the Author of Sure-Footing to His Answerer Mr. J.T. (1666):
Yet I must define whether I will or no, though there be no other occasion why it should be so but onely that you might break a jest, which tickled your Fancy, and so your fingers itcht to put it down; 'Tis a Definition of your own parallell to my counterfeited one, that a Law-giver is one that hath the power of Legislation; And in this you have hit right; for tis just such another definition as mine was.
From The Gentlewoman's Companion; or A Guide to the Female Sex Containing Directions of Behaviour, in All Places, Companies, Relations, and Conditions, from Their Childhood Down to Old Age (1673):
Both these Countrys [Italy and France] have been happy, and may be justly proud in producing so many learned and ingenious men; so many, should I nominate them with their deserved Encomiums, this small Treatise would swell into Volumes; I shall therefore pass them over, but would not have you their Writings, where you shall find plenty of every thing, which shall either tickle your fancy, or furnish your understanding. Having thus adapted you for conversation, let me next show you your deportment therein.
And from Theophilus Thorowthistle, "Sober Reflections, or, A Solid Confutation of Mr. Andrew Marvel's Work" (1674):
How it tickles my fancy to think what a general Jubilee there would be, and how unmercifully it would edifie with your Party to see you set Doctor-Cathedraticus in a Cucking-stool, Lording it over your Female-Auditory, the Water-Nymphs of Wapping, Magisterially maintaining your polemical Arguments and Debates, & tanquam ex Tripode, pronouncing your Oracles concerning the Power of Princes; the Liberty of the Subject; the Authority of the Magistrate; the Obedience of the People; the Duty of the Prelates and Pastors unto their Flock; cum multis aliis:
Early instances of 'tickle the fancy' [Section updated April 26, 2020]
In the full Oxford English Dictionary (1971 edition), the phrase "tickle the fancy" appears under a particular figurative use of the verb tickle:
5. fig. To excite amusement in ; to divert ; often in the phrase to tickle the fancy. Also absol.
It seems possible that the earliest instances of "tickle [one's] fancy" cited by Etymonline are actually instances of "tickle the fancy." The OED's first example of the phrase tickle the fancy is from 1774, but EEBO and Google Books searches find instances from as early as 1642. From Daniel Rogers, Matrimoniall Honovr, or, The Mutuall Crowne and Comfort of Godly, Loyall, and Chaste Marriage Wherein the Right Way to Preserve the Honour of Marriage Unstained (1642):
So it fares in other temptations, of an hideous nature, as Atheisticall thoughts against the Majesty of God, or blasphemous thoughts against the Scriptures, or the essence, and Attributes of God: the basenesse whereof the more we plod upon, (especially while Satans wild fire is in the spirit) the more we are snared therewith. Therefore in such cases as these, the practice of Elisha to the servant of Jehoram, is to be followed: Wee must pray against the tenacity thereof, and force our selves to handle such thoughts roughly at the doore; and in no sort to give place to them: as knowing their Masters feet is not farre behind them. Tosse not thoughts off and on, about passages, which tickle the fancy, and wind in deeplier into it, then it can bee rid thereof, yea though they were most irkesome to it: But take up the sinne in the whole lumpe and bundle: muse of the bitter roote whence it comes, as David did, in his Meditations:
From Edward Reynolds (Bishop or Norwich), Israels Prayer in Time of Trouble, with Gods Gracious Answer Thereunto (1645):
When I heare men magnifie quaint and polite discourses in the ministry of the word, and speak against Sermons that are plaine and wholesome, I look upon it not so much as an Act of pride (though the wisdome of the flesh is very apt to scorne the simplicity of the Gospel) but indeed as an act of feare and cowardize ; because where all other externall trimmings and dresses are wanting to tickle the fancy, there the Word hath the more downright and sad operation upon the conscience, and must consequently the more startle and terrifie.
From Richard Baxter, The Saints' Everlasting Rest (1650/1654):
The fittest temper for a true Believer, is to be in the spirit on the Lords Day: This was St Johns temper on that day. And what can bring us to this ravishment in the Spirit, but the spiritual beholding of our ravishing glory? Surely though an outward Ordinance may delight the ear, or tickle the fancy, yet it is the views of God that must ravish the Soul. There is a great deal of difference betwixt the receiving of the Word with joy, Mat.13.20. and being in the Spirit on the Lords Day, Rev.1.10.
From Nathanael Culverwel, 'The Schisme,' in An Elegant and Learned Discourse of the Light of Nature, with Several Other Treatises Nathanael Culverwel (1652):
And unlesse the word of God were, as the Jewes tell us of the Manna, though very fabulously, (yet we have the same in the Apocrypha in the 16th of Wisdome; that whatsoever Character, or Idea of taste a man shap't to himself in his fancy when he was eating the Manna, as most pleasant and delightful to him; it serv'd to the appetite of the eater, and was temper'd to every ones liking:) unlesse the word of God had so many severall relishes, agreeable to every ones liking: Even this, though Angels food shall be loathed, and nauseated, and surely this argues a carnal Spirit. Must the νομος[?] βασιλικος bow to you? and the Gospel of the Kingdome become so basely serviceable, as to do homage to your lusts? Must that word which should search the Conscience tickle the fancy, and feed a worme of curiosity that never dies?
From Christopher Love, The Naturall Mans Case Stated, or, An Exact Map of the Little World Man Considered in Both His Capacities, Either in the State of Nature or Grace (1652):
Smal sins are committed most commonly with more complacency and lesse reluctancy, then great sins are; unclean thoughts do please the heart and tickle the fancy, and content the minde of a man, and are committed with a great deal more complacency & delight, and lesse reluctancy; who would strain at a gnat? Now it layes your souls upon more guilt when you commit the smallest sins with delight and contentment, and satisfaction, then if you did commit great and gross sins, if you labor to resist them, and strive against them.
From Thoma Blount, "Instructions for Writing and addressing Letters," in The Academie of Eloquence Containing a Compleat English Rhetorique, Exemplified with Common-places and Formes Digested into an Easie and Methodical Way to Speak and Write Fluently According to the Mode of the Present Times (1654):
And though with some men you are not to jest, or practise capricio's of wit; yet the delivery of the most weighty and important matter, may be carried with such an easie grace, as it may tickle the fancy of the Reader, and yeeld a recreation to the Writer, as Plato observes, lib. 6. de Legib.
From Edward Reynolds, "Joy in the Lord Opened in a Sermon Preached at Pauls, May 6 (1655):
Thus are Believers to rejoice in Christ: And that, 1. Greatly, again and again. Other delights may please the senses, tickle the fancy; gratifie the reason; but there is no joy that can fill all the heart, but the joy of the Lord, Zeph. 3. 14.
And from John Brinsley, The Spirituall Vertigo, or, Turning Sickensse of Soul-Unsettlednesse in Matters of Religious Concernment the Nature of It Opened, the Causes Assigned, the Danger Discovered, and Remedy Prescribed (1655):
It may be they are such doctrines as do please and tickle the fancy through the Novelty and strangenesse of them. They are such Doctrines as the Text speaketh of, Divers and strange doctrines. And strange it is to think, how such doctrines do sometimes affect the Hearers of them; having nothing else to commend them but onely their Novelty and strangenesse. They are New and strange. And Oh! how taking is this with many?
Most of these instances of "tickle the fancy" are from the works of clergymen who show no signs of intending the expression in a double sense.
Early double-entendre use of 'tickle [one's] fancy [New section, April 26, 2020]
The earliest instance that I've been able to find of "tickle [one's] fancy" in an unmistakably sexual sense is from "A Song," in Westminster-Drollery, or, A Choice Collection of the Newest Songs & Poems Both at Court and Theaters by a Pperson of Quality (1671–1672):
Then away with a Lady that's modest and coy, / Let her ends be the pleasure that we do enjoy; / Let her tickle her fancy with secret delight, / And refuse all the day, what she longs for at night: / I believe my Selina, who shews they'r all mad, / To feed on dry bones, when flesh may be had.
This song shows up in multiple collections published from 1671 to 1676.
The next instance I've found is from A. Marsh, The Ten Pleasures of Marriage Relating All the Delights and Contentments That Are Mask'd Under the Bands of Matrimony (1682):
And a third again relates how her husband tarried above a fortnight from home, after that she was out of Child-bed; but comming then home, he did so claw her off and tickle her fancy for her that very precisely upon the nine months end, she was brought to bed of two children.
And then from Thomas, D'Urfey, The Intrigues at Versailles (1697), an instance that may be playing on the double meaning:
Sir B. Gives me the charge of all her Money and Jewels; looke[e] here are the Keys of her Scrutore, you may see by this I [h]a[v]e tickled her fancy; here is a Diamond Ring too I got from her this morning, she will part with any thing for a nights Lodging; the Jade knew I [am] a swinging Bed-fellow.
Conclusions [Updated April 26, 2020]
It seems very possible that the earliest wording of "tickle [one's] fancy" was actually "tickle the fancy," where the verb tickle was understood figuratively to mean something like "amuse" or "divert" and where the noun fancy was understood to refer to "imagination" or "thought" or "mental activity." The fact that so many of the earliest recorded uses of the phrase in EEBO and Google Books search results come from religious figures suggests that "tickle the fancy" was not understood at the outset to allude to anything beyond its obvious figurative meaning.
The earliest instance of "tickle the fancy" that I could find is from 1642, and the phrase seems to have been common by the 1650s. Expressions of the form "tickle one's] fancy" emerge by 1655 but appear to be less common than "tickle the fancy" through most (and perhaps all) of the remainder of the seventeenth century.
Examples of works using "tickle [one's] fancy" as a sexual double entendre go back to at least 1671–1672, when it appears in a popular song. However, such usage evidently did not taint the phrase significantly to dissuade serious-minded authors from continuing to use it. The same might be said of the phrase as used in the present day by a great many people who have no intention of being salacious.