Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time
As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.


That's exactly the solution I would go for. 

Store a mapping of $\langle x, freq_x\rangle$ in the BST. Because each $x$ will be unique in the bst you will be able to search for the frequency with just $x$.

insert becomes 

if x is in BST then
    replace &lt;x, freq&gt; with &lt;x, freq+1&gt; in bst
    if freq+1 &gt; max_freq then
        max_freq := freq+1
        max_x := x
    endif
else 
    insert &lt;x, 1&gt; into bst
    if max_freq = 0 then
        max_freq := 1
        max_x := x
    endif
endif


You don't really need a tree, instead a hashtable would drop the complexity down to O(1) for every access and O(N) for init.