You can check the demo example about floating axes for several uses of rotation. In this case you will only rotate the axes and than make the normal call for a legend.
You'll need to make the adjustments for position of legend, limits of the plot and so on, but a quick look at this example should provide you the logic behind it:
from matplotlib.transforms import Affine2D
import mpl_toolkits.axisartist.floating_axes as floating_axes
import numpy as np
import mpl_toolkits.axisartist.angle_helper as angle_helper
from matplotlib.projections import PolarAxes
from mpl_toolkits.axisartist.grid_finder import (FixedLocator, MaxNLocator,
                                                 DictFormatter)
import matplotlib.pyplot as plt
def setup_axes1(fig, rect):
    """
    A simple one.
    """
    tr = Affine2D().scale(2, 1).rotate_deg(30)
    grid_helper = floating_axes.GridHelperCurveLinear(
        tr, extremes=(0, 100, 0, 100))
    ax1 = floating_axes.FloatingSubplot(fig, rect, grid_helper=grid_helper)
    fig.add_subplot(ax1)
    aux_ax = ax1.get_aux_axes(tr)
    grid_helper.grid_finder.grid_locator1._nbins = 4
    grid_helper.grid_finder.grid_locator2._nbins = 4
    return ax1, aux_ax
fig = plt.figure()
x = range(100)
y = x + np.random.randint(-10,10,100)
ax1, aux_ax1 = setup_axes1(fig, 111)
aux_ax1.scatter(x,y,c='green',label='green')
aux_ax1.scatter(y,x,c='purple',label='purple')
ax1.legend()
plt.show()
This particular recipe (adapted from the link at the top of this answer) results in this:
