How can I make vegetarian marshmallows?
This is definitely one of those times where I wouldn't recommend substituting agar for gelatin; it's simply far too stiff for marshmallows.

If you can get hold of some methyl cellulose, it works great for marshmallows.  Unlike other gelling agents, methyl cellulose hydrates in cold water and sets when heated, so you can roast it with direct heat and it will still hold its shape.  All you need is methyl cellulose, vanilla, sugar, and water.

You can find the full recipe at playing with fire and water (see "methocel marshmallow", second on the page).