fluffiness of medu vada without baking soda
I believe baking soda was a recent addition to medu vada and is not a required or traditional ingredient. It helps to make the vadas fluffier and it might make it easier to have a good result if your batter consistency is to not quite right, but it isn't required. Personally I find that it affects the flavor so I don't like to add it.

I think you can just leave it out entirely.

The keys to having fluffy vada without extra leavening would be oil temperature in frying and the amount of water in your vada batter. Also, whip the batter again after adding the seasonings so there is a lot of air in the batter to begin with.

The oil should be hot enough that when you drop a bit of the batter in, it immediately puffs up and floats to the top and starts cooking. If it immediately starts turning color, the oil is too hot. If it doesn't float, the oil is too cool.

If the oil is too cool, the vada will soak up a lot of oil and it will be soggy and dense and won't rise. If the oil is too hot, the outside will burn before the inside is cooked.

The batter should be almost like a very soft dough. If you hold a clump of it in your palm you should be able to hold it and not have it run out between your fingers, and it should hold the shape you give it. You should also see that it is a bit lighter and fluffier when you whip it. If it has too little water, it will tend to stay clumpy when you whip it up.

If the batter has too much water, it will not hold its shape and won't support the rising action and will be soggy. If there is not enough water it will be too dense and not rise well, so it can be hard after cooking. 

It is easier to add more water if the first one is too firm, though, so err on having too little water if you aren't sure and test the first one you make.

Here's a recipe with a video so you can see how the proper texture looks. I really like Manjula-ji's recipes and demonstrations, they are very clear and easy to follow, so hopefully this video can help with the batter.