I agree - the hard part is how to attach the lego sheets to the underside of the pedals. Some sort of glue I suppose. But anything that would hold securely might be difficult to remove later.
My first thought on the overall idea was "why?" but on reflection, I can see some appeal. Velcro gets filthy pretty fast. There's nothing quite like the accumulation of dust, dirt, animal and human hair and other grunge that you'll find in an old piece of Velcro that's been attached to something you step on in bars. I imagine lego sheets would stay cleaner or at least be easier to clean.
Still, I think Velcro will remain the most practical solution.