I think, since future Bill and Ted appear to the earlier Bill and Ted, and Rufus directly assists in creating his future, I think we have to assume that all of those historical figures always experienced those things, and then returned to their timelines with knowledge of the future. Napoleon rode the waterloops before Waterloo. Socrates played catch with Billy the Kid. Those are historical events, as much as Rufus and Future Bill and Ted helping present Bill and Ted pass their classes.