If the set of all possible states changes each time, how can Q-learning "learn" anything?
if the length and height of the rectangle are random, as well as the starting position and the location of the Treasure, how can the bot apply the knowledge acquired to the new problem? 


You have two possible approaches here, depending on how the problems are being presented to you:


If the agent has time to learn/plan on each environment separately, then you need an agent that has capability to learn each environment. A simple tabular Q-learning agent already has this capability, up to a certain size of problem (where the number of states and actions would fit in memory and can be iterated over in simulation enough times). Beyond that size, provided you can come up with a fixed feature set capable of representing any shape and size of problem that the agent could be presented with, and used e.g. DQN or other approximation technique, then you still have a generalised learning bot.
A bot that is generalised during training to attempt to solve new instances with variation needs to be trained with many variations and more state data. If shape, size and layout of the maze can change between episodes, then this data must become part of the state. This can expand the state space a lot, and requires different representations. A simple representation of grid spaces would be actual map of the grid as a rectangular "image", assuming the agent start, walls and goal position could be almost anywhere within the space. If the maze has lots of objects, then you can put each object type into a separate "channel" and use a Convolutional Neural Network as part of the Q function approximation. If the area is more sparse with just a few objects (e.g. just the agent, a single blocker and the treasure) then it would be easier to use a direct vector representation of positions of the objects and use a fully connected neural network.


For a toy problem where key positions can change between episodes, yet this still can be solved easily by a tabular agent, see Open AI's Taxi-V2 which is an implementation of a classic control problem where the locations of a sub-goal and goal are randomised on each episode.