Possibility of faking someone's public key
If Alice keeps her correspondent's public key in a database, spreadsheet, text document; then it's feasible that your scenario would work.
However, most (including Alice hopefully) would only trust public keys that have been certified as authentic. There are two mainstream methods by which this is currently done:
Certified by a central authority
The public key is certified by an organisation specifically set up for this task - these are called Certification Authorities (CA).
The CA will have checked Bob's credentials when he asked them to certify his public key. Bob can then send his certified public key (commonly known as a certificate) to Alice and his many other friends/colleagues.
If Alice only trust public keys that have been certified by trusted CAs then your scenario now fails. You cannot sneak in your public key as it hasn't been certified and consequently Alice won't trust it.
You can approach the CA with your public key, but they'll only certify that it belongs to you - not to Bob (or Alice, or anyone else).
This method is used by the commercial CAs which sign the certificates used for asserting the identity of resources on the Internet (such as this site). Organisations may also operate their own CAs.
Certified by friends and/or colleagues
An alternative to the above method is for Alice to confirm with friends/colleagues that already correspond with Bob as to whether his public key is genuine. They'll know this by confirming with others, or by confirming with Bob himself (maybe a face-to-face meeting). This way, the trust spreads like a spider's web, leading to this concept being called a web-of-trust.
This latter method is used by Pretty Good Privacy and Gnu Privacy Guard.
The CA isn't the be-all and end-all of the problem though. In your scenario you have compromised Alice's device, which means you could configure her device to trust public keys certified by another CA - namely yours. You can now certify your public key masquerading as Bob's and Alice would unwittingly trust it.
However, CAs come into their own when we diverge slightly from your question and consider 'Bob' not to be a person, but instead to be a new resource on a extremely large network such as the Internet. In such cases, the Web-of-Trust model would not work simply due to the scale of the problem of managing all the public keys.
In other words, a CA would not be of much benefit in a scenario which consists of a single one-to-one relationship, such as Alice and Bob in your question, because it simply changes the test Alice implicitly makes from Do I trust Bob's public key? to Do I trust that my device hasn't been configured to trust additional CAs?
However, in a one-to-many relationship, such as the Internet, a CA will remove the requirement to somehow check each and every public key before use and replace it with checking the configuration of your device (which we all do without question!).
Of course, in the real world, if you successfully compromise Alice's device, whether you change Bob's public key is immaterial in the bigger picture.
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).