The person who said that may have meant to add the sense of potentiality to the whole act of 歩きながらメッセージを送る. Though it sounds incomplete as an independent sentence, it doesn’t sound particularly unnatural in a subordinate clause (provided it is not a quote).
As an independent sentence,...
Your sentence doesn't quite sound right to me, although I can't quite point to a grammar rule to explain why. You might be correct in assuming that the potential form of the main verb renders it as a stative verb and doesn't sit right with the ～ながら. However, I think that if you insert a topic marker は then the sentence would work.