Words like "zounds" are not medieval, but are inventions of 19th C. story tellers. Words like fuck, as mentioned above, were normal language before the imposition of latinate and old french forms by the Norman invaders.

There is no evidence of "blimey" before the 19th c. "'strewth" also first appears in print in the 19th c, but the use of 's is old, so it can't be ruled out absolutely.
There also is a fair bit of myth. "Bloody" had nothing to do with the Virgin Mary or the blood of Christ, but was applied to the habits of the "bloods" or aristocratic rowdies at the end of the 17th and beginning of the 18th C. (see Oxford English Dictionary).
The one from Shakespeare posted by Mesophist is a good example of the few we have from the English renaissance, and similar phrases undoubtly were medieval as well.

I have no doubt that swearing has always been colorful, but our ideas of it come mostly from the 19th century writers and not from fact.