I remember doing this for Minnesota once so I'll probably do it again. It's quite easy really, MN-01 can remain intact, MN-07 and MN-08 swap precincts to get MN-07 an Obama win and in the metro you have to do some weird carving and split Minneapolis to get some exurbs in with urban seats and then turn the old Bachmann seat into a weird sort of St. Cloud to inner suburbs strip. Barely for Obama, but won nonetheless.
Can you do it without chopping Mpls or StPaul?
McCain won the old MN-02, MN-03 and MN-06 combined, so not out of those three alone. But if you added the suburban parts of MN-04 and MN-05 it's probably possible, though it'd require a strip running form at least one of the inner cities to exurbs.