The Tag column size is 64. If I make this larger in the database, will it be truncated once it is loaded into memory?

According to modules source code Tag's max size is hardcoded and will be truncated. But this is not a bit problem. You can keep capabilities list in htable and only put a key for this htable info to the tag.

Through which list do I need to iterate? You mentioned the data is stored in a hash table, what is the name of this hash table?

load_gws() creates a list of gateways and next_gw() fetches them one by one.
After calling load_gws() you can just call next_gw() which puts gateways tag to the "tag_avp". If current gateway doesn't have requested capabilities just call next_gw() again.

Basically for each call I need to call the load_gws() function, which is O(N) * O(M).

What if I take a different approach and call a stored procedure (for each call) which does the selection of a gateway based on the supplied criteria.

Of course the tables would be optimized with indices for the best possible performance.

When comparing load_gws() (O(N) * O(M)) with the stored procedure approach, would there be a huge performance loss when taking the stored procedure approach?

Who knows.. You can test it and share results with community :)

I know this approach brings a whole new set of problem with availability and the loss of features, but for now I’m only interested in the performance aspect of both methods.

Actually going this way you don't need LCR module at all. You can call stored procedure, lua/python/perl/... script, or request an external system using radius/xmlrpc. But be careful making blocking operations from a script or have enough number of kamailio processes.