Hallo Yves,

generell verboten ist das Radfahren auf Europastraßen nicht, oft aber auf einzelnen Abschnitten. Dann gibt´s meist aber ausgeschilderte "Umleitungen" für Radfahrer. Das heisst aber nicht, dass es erträglich ist dort zu fahren, wenn es nicht verboten ist.
Die Strecke Gävle-Uppsala habe ich vor ein paar Jahren ohne E4 geschafft, es war einer der schönsten Abschnitte unserer ganzen Tour.
Ich kann ja mal die grobe Route auflisten (für Dich jetzt umgedreht in Richtung Gävle):

Uppsala auf 272 verlassen, hinter Östervåla runter von der 272, über Horsskog, Hadeholm und die Halbinsel "Ön" nach Hedesunda. (Den Hedesundafjärden (Dalälven) dürfte inzwischen eine Brücke überspannen, statt der Fähre damals.)
Von Hedesunda entweder die 67 oder besser die Landstraße zwischen der 67 und E4 über Finnböle, Åsberga bis Gävle.

Das dürften kaum mehr Kilometer sein als auf der E4. Zur 272 kann man natürlich noch parallele Alternativen finden, aber die war nicht übermäßig befahren. Besonders die Gegend um den Hedesundafjärden (Ön) war sehr schön. Einziges Problem damals war, dass der einzig erträgliche Campingplatz in Gävle (Citycamping mit Dixi war indiskutabel) in Furuvik lag. Das passt nicht gut zu dieser Route weil es 5-10km östlich von Gävle liegt, man muss also fast mitten durch die Stadt, ist aber immer noch besser als E4...

Gruß
Benjamin