You can employ the linear regression algorithm even for categorical data. The point is that whether your data is learnable or not. For instance, take a look at your data, and see whether an expert can really find the output by taking a look at the input vector. If it's possible, your task can be learnt using linear regression method.
About linearity, the point is that linear regression can also learn nonlinear mappings. You just have to provide enough higher order polynomials of the current feature space you have which is not an easy task. For instance, you can expand your current feature space by adding the square of each feature to the current feature space. You will observe that it may have better performance than the usual case if your mapping is not linear, but you may still have error. Consequently, you have to supply more polynomial features, but you do not know which to use.
An alternative to linear regression which does not need to add extra features is multi layer neural networks (MLP). You can simply use them which can learn nonlinear mappings. You can take a look at the official page of SKlearn for applying them. Furthermore, you can take a look at here for applying them.