Store-bought marshmallows (and most homemade marshmallows) are gelatin-based, which means they'll melt above 40° C. No chance of surviving a bake.
I have, on occasion, seen "rocky road" type brownies with actual marshmallows and I suspect that they are either not conventional brownies or not conventional marshmallows.
You could probably create a bake-stable marshmallow by adding methyl cellulose along with the gelatin. MC is the typical additive in a vegan marshmallow; it gels when hot and "melts" when cool. Using both of the above additives (and perhaps several more) could theoretically render a marshmallow with a continuous gel temperature range. I'm not even going to try to speculate what the ratios or other additives would be - this is generally the domain of commercial food packaging, food scientists, etc. - it's pretty complicated even if you're familiar with the main molecular gastronomy concepts.
Another alternative would be to bake the brownies plain, possibly overbake them a little, then grind them up to the consistency of large crumbs, mix them in with the marshmallows (and nuts and any other additions you want), and put them back together with water and/or corn syrup. I've made rum balls from ground-up brownies this way and they hold together surprisingly well, although they obviously won't pass for fresh-from-the-oven brownies.
As a last resort I'd go with JSBangs' suggestion and go with a marshmallow creme product (e.g. Marshmallow Fluff). It's basically just syrup, vanilla, and egg whites as a thickener. It won't have the texture of a real marshmallow, but because it's based on egg, the texture that it does have will withstand the heat.