Partout has a greater connection with garer so its expected location is the one of the first sentence. Your second one is still grammatical but less natural. Maybe "You can everywhere park" would be similarly odd.
With a more complex phrase, this location1 of partout would be idiomatic:
Vous pouvez, partout et à toute heure, vous garer dans le parking de l'hôtel.
What would also be possible is:
On peut se garer où ?
On peut partout !
Comment from @Vincent:
With an infinitive, the adverb can be preposed, but it's not very natural for a rhematic word, and therefore, it has en emphasizing effect:
Vous pouvez très bien partout faire état de vos opinions, mais je vous suggère de faire attention dans certains lieux.
1 @Vincent rightly commented that my examples cannot be considered to match the requirements as in the first one the phrase partout et à toute heure is detached from the rest of the sentence by commas, and in the second one, se garer is implicitely located between peut and partout.