Conferences generally start out small, without compensating any of the speakers and without providing travel assistance.
But, then that really depends on your starting budget, and not providing travel assistance will keep you from getting some speakers.
It also matters if you're trying to make money off the conference, are are just doing it for fun. Obviously, you have to convince people you are going to provide $500 worth of value if you charge $500. If you're charging that much, however, the keynotes probably expect to at least get some travel assistance, if not a cut.
I think cold calling a few potential keynotes isn't a bad thing, especially if you're willing to provide travel assistance. If your not, and depending on who you are contacting, cold calling a completely random "semi-famous" person might not go over well.