"Прошли весь город пешком" - sounds kinda odd to me, because it is really seldom when some city or town is just a narrow point on a road that is supposed to be walked through. Somehow "через весь город" is used more often, imho. Without "через" (through) there still is a little doudbt if you meant "walking around" or "walking trough".

Fine examples without "через":
-Пройти испытание
-Пройти компьютерную игру
-Пройти тему (в учебе)

These are things that are supposed to be elaborated \ explored following finishing of your current activity.
While "Пройти через" - stands more like going from A to C through some B point (the main targer is C).


So,

"Пройти тему" - discover smth (reading \ playing \ working)
"Обошли весь город" - to walk by foot around the city, watching sightseeings
"Прошли через весь город" - to walk by foot from west to east or north to south with purpose.