How does Alice know Bob's public key?
There are several ways for Alice to verify Bob's public key, each with their own pros and cons.
Direct and in person
This is probably the most secure approach. Alice and Bob meet in person, exchange and possibly sign each others public keys. This would make it virtually impossible for anyone to tamper this process.
The disadvantage should be readily apparent: This approach is not feasible for anyone who doesn't meet in person regularly. People across the globe would need to invest considerable amounts of money to be able to meet each other, just to exchange keys.
Via Bob's Server
Bob has a web server, secured by proper TLS, and offers his public key as a download there. While this is much more convenient than meeting Bob in person, it also carries the risk of compromise.
If Eve was able to access Bob's server and generated her own keypair, she could replace Bob's public key with her own. This would become apparent once people tried to send messages to Bob and he would not be able to decrypt them, but at this point it might already have been too late.
Via a Key Server
Instead of hosting the key himself, Bob uploads his key to a key server and just links
to it. This is very similar to the approach before, but migrates the risk from Bob to whoever controls the key server.
Additionally, an attacker could create a fake public key in Bob's name ("Evil Bob"), and additionally create fake public keys for Bob's friends, creating a fake web of trust around "Evil Bob".
Via "direct messaging"
A naive approach would be to message Bob on Twitter, WhatsApp or similar platforms, asking him for his public key. The problem here is that you can't really verify if it's really him. An attacker might have gained access to his account and distribute fake public keys for "Evil Bob".
VoIP systems might be better, but are not as perfect as people might think.
Is is possible to deceive someone, so that they would use a fake public key?
Yes, as detailed above. Any scenario in which Bob does not directly and personally give you the key could be compromised.
There are protections however. People can sign Bob's key, thus vouching for Bob. The more tightly interwoven these connections are, the more difficult it becomes to fake a key. Nonetheless, it is possible.
How can Alice protect herself from Eve modifying Bob's public key on her device?
The assumption is that Eve was able to exploit Alice's device in order to modify Bob's private key.
This scenario is difficult, but not impossible. Every key has a fingerprint, actually two fingerprints: "long" and "short", which identify the key. If Alice were to remember the long fingerprint, then it would be unfeasible for Eve to create a collision and insert a key that she controls and that is similar enough for Alice to mistake it for a legitimate key.
If she only memorizes the "short" fingerprint, then it becomes technically feasible, although high-value keys would likely be targeted before average people like Alice and Bob.
A web of trust would also help in this case, as even if a fake web of trust would be generated, Alice would not trust any of these keys, as she would need her own private key to sign it (and Alice has protected her private key with a strong random password that Eve does not know).