Did the accent in "without" shift from the first syllable to the second in the past?

With the stress on the second syllable, the line would not scan.

Herein lies the problem. Milton's "blank verse" is notoriously irregular, so much so that whole careers have been spent trying to elucidate the precise rules underlying its metrical structure. Indeed, an important part of Milton's poetic legacy was his challenge to the very idea of a metrical "foot" as the fundamental unit of rhythm. This is a fascinating topic but, alas, much too complicated to get in to here. (If you're interested, I would suggest this essay by John Creaser as an excellent entree to the subtleties of Milton's prosody.) Suffice it to say that one should exercise extreme caution when attempting to make inferences about historical pronunciation from considerations of scansion in Milton. For instance, in the passage you quoted from Book I of Paradise Lost, interpreting the third line as a strict iambic pentameter would yield:

 x  /   x   /  x    /   x    /       x    / 
Regions of sorrow, doleful shades, where peace

Should we therefore, in reading this line, pronounce the first word as re-GIONS? No! As Robert Bridges wrote in his seminal 1889 study Milton's Prosody:

The intended rhythm in P.L. is always given by the unmitigated accentuation of the words of the verse as Milton pronounced them; nor does the qualification 'as he pronounced them' raise much uncertainty.

As a matter of terminology, the use of "Regions" in the line quoted above would traditionally be called inversion (i.e., the substitution of a trochee for an "expected" iamb). Yet, if one examines the first few hundred lines of Paradise Lost, one will find only a handful that scan exactly as "expected" without violence. Indeed, one can easily find far more radical deviations from the iambic "ideal." By way of example, Bridges offers the following line from Book III:

  /       /       /      /           /
Shoots invisible virtue even to the deep.

According to Bridges, we should read this as "SHOOTS in-VIS-ible VIR-tue EVen to the DEEP," which is both intuitively reasonable and clearly not iambic pentameter. I will refrain from discussing Bridges's actual theory of scansion, as it is irrelevant (and somewhat controvertial). However, the basic point about pronunciation is absolutely spot on: one must never torture Milton's verse into bizarre patterns of word stress just to bring it in line with some imagined ideal of iambic pentameter---let alone interpret its noncompliance with that imagined ideal as evidence of an actual difference in pronunciation.

At the risk of beating a dead horse, it is worth consulting some early modern sources to test our suspicions about the pronunciation of without. Shakespeare, as you have already pointed out, usually places the word so that its second syllable coincides with the ictus of a putative iamb (though even he will depart from this pattern when it suits him):

'Tide life, 'tide death, I come without delay.
(A Midsummer Night's Dream, 5.1.2047)

O villains, vipers, damn'd without redemption!
(Richard II, 3.2.1539)

but

As, by my faith, I see no more in you
Than without candle may go dark to bed
(As You Like It, 3.5.1691-92)

And all the number of his fair demands
Shall be accomplish'd without contradiction.
(Richard III, 3.3.1764-65)

And here is the entry for without in Thomas Dyche's Spelling Dictionary of 1723, the first such dictionary to indicate word stress (via accent marks):

Of course, Milton had already died some 49 years before this work was published (and Shakespeare some 58 years before that!), but this does at least establish that any hypothetical fad in the pronunciation of without would have to have died off before the 1720s. Surely the parsimonious explanation is that there was no such fad.