Milton Friedman famously said that you can’t have a welfare state and open borders. I disagree. In many respects (not all), you can have open borders and a welfare state.
What we think of as the welfare state encompasses many different programs, many of which are not handouts. Social Security for example is mostly a forced savings program. For these types of insurance programs there is no problem at all as, for the most part, a person has to work and pay into the program to get money out of the program. For programs like schooling there is also no problem–even if the schooling is provided free to immigrant children–because the schooling leads to higher wages later in life which are taxed. In these cases, the immigrant children are really just receiving a loan which they will have to pay back from their own earnings later in life. The story for basic health is similar. Thus, the only cases where there is a worry about excessive transfers from citizens to immigrants is in pure handouts or health benefits to say the elderly. In these cases, I would simply say that such benefits are not available to immigrants or only available after five years or some such time period.
Addendum: I gave this answer in an interview for a Brazilian newspaper. You can read the full interview here although it is in Portuguese.