I'm looking for a word that could describe a person who is very gullible and easily trusts people.
My specific example is Fortunato from Edgar Allen Poe's story: The Cask of Amontillado
Edit: the character's name is Fortunato.
Credulous is a good alternative to gullible.
Not to sound too obvious, but what is wrong with "trusting"?
John was very trusting, some might even say gullible.
Your question is a little unclear because gullible doesn't just mean "easily trusts others", it really means "easily deceived," or "easily taken in." For sure, a gullible person might be trusting, but I don't think all trusting people are necessarily gullible.
Maybe you are looking for the word 'naïve'?
I think you answered that yourself:
In a modern context the noun pushover can refer to someone who is easily led, easy to influence or convince, or can be drawn into situations with little effort.
I think dupe is the perfect word to use!
Gullible and naive both suggest that the person trusts too easily, or is easily deceived. I suggest choosing "trusting" instead. It seems to describe someone who trusts easily versus someone who trusts too easily.
If you'd like an informal term, "shnook" is humorous.
Otherwise, there is also simpleton, chump, and gobemouche.
A somewhat negative way to convey this would be to call a person a sucker. As in "There's a sucker born every minute", often credited to P. T. Barnum.
You might say the person is unassuming, an ingenue, or a "babe in the woods."
I think it depends on the tone of the sentence. Compare the tones in the following phrases:
In French it would be "candid", but if I candidly trust Google define operator, the meaning has shifted to "Truthful and straightforward; frank".