Power pins are required for the gate to have gain, which is necessary for fan-out, meaning that one input can drive an output that (reliably and quickly) drives many more inputs on other gates (which may have high capacitance loading or current requirements). That's where the simplified textbook examples of gates typically fail the real-world usefulness test.
There's also no way for a gate without a power (ground) pin to source current if no inputs are high (and vice versa for sinking with all inputs high and no ground pin).
In some cases if the power connection is missing from a CMOS gate it can continue to function (albeit poorly) because the protection networks act as an "OR" gate, so if any input is high, the Vdd node sees that input voltage minus a diode drop plus. If there is a bypass capacitor, it may even continue to function even if all the inputs momentarily drop low.
This has fooled more than one person troubleshooting a circuit, since they might expect the gate to behave more passively without power deliberately applied. It's generally a very bad idea to do this intentionally, though there may be some cases where it is justified (and it is guaranteed to get clucks of disapproval and close inspection from 3rd parties). One of the issues is potential latchup. There are others.