Is there a Diplomacy variant that does not contain stalemate lines?
Erlend Janbu's variant South America v. 3.2 for four players was designed with the explicit aim "to create a variant where there are no stalemate lines." In a 2001 article on the variant he admits that he does not know for sure whether there is a stalemate line in his variant, but "I and others have searched, and after 100 games, no game has ended in a stalemate." He claims in that article that only "[f]ew variants are stalemate-free," but unfortunately he does not name any. Until one could prove that there is indeed a stalemate line in the South America variant, the answers to your main questions should be positive: yes, it is possible to design a stalemate-free board and yes, it has been done before.

As to how the lack of stalemates would affect the game, it might be worth reading what Andy Schwarz has written on his variant Hundred (based on the Hundred Year's War). As he wrote in an article from 1996, "eliminating draws was a big part of the design of Hundred." This has encouraged solo wins and alliances-shifts, making the game very dynamic. This should also apply to any variant which reduces or eliminates stalemates.

As to variants which avoid stalemates by means of changes to the rules, Stephen Agar wrote about this specifically in his article from 1992, "Designing Maps for Diplomacy Variants," where he notes that "[s]ome variants avoid stalemate lines through the rule mechanics." The only example which he gives is the Multiplicity variant, where multiple units can occupy a single space.