You have some interesting ideas. Moving the Eifel Tower scene to S3 could work if you cut out most of the dialog. Or maybe dub everyone but Lois and Sup in French and then write some subtitles!
In your rough edit, did you edit out all of the horrible attempts at humor? And does the movie still make sense?