¿No sirve para eso Redim?
Código:
Dim arr() As Byte 'array sin dimensiones
dim1 = CInt(Text1.Text)
dim2 = CInt(Text2.Text)
ReDim arr(dim1, dim2)
Y si quieres usar una estructura de datos... Los arrays de VisualBasic no son otra cosa que SAFEARRAY's. Buscando en la documentación de la API de Windows seguramente encotrarás información útil.