If you put eco complete over gravel some will sink and if you put enough it will cover the top, it may end up like you said, a sandwich. Also, if you combine the two, every time you disturb it some gravel will end up topside, giving a two color tone. I wouldn't do it, I have eco over gravel and I wished I hadn't done it. About changing the gravel, you can do it with fish in it, just buy large enough diameter hose that gravel can be siphon, no mess. Putting Eco complete in tank with water is not messy, I've done that also with many fish in it with no problem. You may need to do extra water change it it becomes too cloudy, but eco is not messy at all, that's what I like about it. I would at least empty 2/3 of the water, it's a little easier to set the new substrate, and just save the water.