The problem you describe is how Alice knows that the public key used for signing actually belongs to Bob. As you correctly realized it does not work if Alice receives the public key only together with the signed message and has no way to verify that the key belongs to Bob, because in this case Eve could simply replace both key and signature with their own.
A way to deal with the problem is to make sure that Alice gets Bobs public key up front in a trusted way, for example during some personal meeting. This is usually only possible in a few cases so instead of having this direct trust one can use a derived trust, i.e. Carl gets the key from Bob, Alice gets the key from Carl and Alice trusts Carl that this is really Bobs key. You can implement such trust relationships with signatures to get a more scalable trust network with more parties. This is the basis for the Web of Trust used by PGP but also for a the more centralized Public Key Infrastructure used for S/MIME and also for HTTPS.
Using such trust networks it is also possible to send the public key together with the message as long as the public key itself is signed by a trusted party. For example could Bob ask Carl to sign Bobs key using Carls key and then send a message to Alice signed with this signed key. If Alice trusts Carl, i.e. has Carls public key, then Alice can not only verify that the message was actually signed by Bobs key but also that this key actually belongs to Bob because she can verify Carls signature on it.