Now I can put 4 different textures on a wall:

and it has virtually no negative influence on performance, because every piece of wall is still represented by an integer, eg. 0x01020304 means there will be texture 1 put on side 3, texture 2 on side 2, texture 3 on side 1 and texture 4 on side 0 . Proper texture is chosen by only two bitwise operations. And your CPU loves bitwise operations. This kind of representation also introduces a limitation of 255 wall textures per map, but I reckon it's more than enough for a raycasting engine.