Fixing I-35 through downtown Duluth would honestly be straightforward compared to punching a freeway (or even a parkway) through Duluth's north side. Congdon Park wouldn't be overly challenging, but Lakeside and Lester Park involves either a convoluted bypass or punching through neighborhoods. It may still be cheaper than the alternatives, however.
You're not going to punch a 3-4 mile tunnel through Lakeside or into Lake Superior. A causeway bypass into Lake Superior is also a non-starter - even if you could get folks to accept it, the weather would never make this feasible.
What's left is a northerly bypass of Duluth, which would run a minimum of 25 miles and involve a lot of property displacement. You also, for better or worse, cut off downtown Duluth from North Shore tourist traffic.
Whatever the solution, Duluth and MnDOT should be engaging in the discussion now. The North Shore traffic issue isn't going to go away, and the longer its put off, the more expensive the answer is going to be.