Tough, but possible. I think the only challenge you might come up against is variety. I don't know how many carbs you're planning on incorporating, but you may want to consider adding beans to your diet, as they carry a good amount of protein and fiber, but more carbs.

You may also have to rely on packaged food a bit more than someone who eats dairy and eggs. For example, using vegan burgers, vegan hot dogs, etc., as well as tofu might become your staples in terms of protein, as well as veggies and good fats.

Here's a protein shake I make every morning that you can easily make vegan. It's a nice way to start the day.

Chocolate Protein Shake
1 cup cold water
1/2 cup soy or almond milk (soy has more protein)
3-4 oz silken tofu
2 tsp unsweetened cocoa powder
2 tsp natural nut butter (peanut or almond are good)
1 tsp psyllium husk powder (for fiber and it also thickens the shake)
sweetener to taste (I like it sweet, so I use 2 tsp xylitol, a bit of stevial, and 1 packet splenda)
1 scoop vegan protein power (like soy powder - I use Nature's Way Energy unsweetened, unflavored protein powder, which, I think is vegan)
Ice

Hope that helps!

Tam