I’ll start with the last one:
No, they will not be “redirected”, they will access your post with their old link.
To give you an example from a blog of mine – permalinks set to year/month/day/post_title
https://www.transycan.net/blogtest/2007/09/10/static-frontpage-combined-with-dynamic-content/
but if you access the post with the ugly (=default) permalink:
https://www.transycan.net/blogtest/?p=151
it is there and you don’t get a 404 Not Found message.
Which, BTW, is NOT true if you would go the other way around: having a link set to a nice permalink and after changing it back to the ugly/default – visitors would get a Not Found error.
And for the first question, basically that would happen… and the new link’s structure would depend on what structure tags you would use in your permalinks.
As for the big G… it will pick up after a few weeks your new permalinks when it re-indexes your blog.