Welcome to the confusion one always encounters when trying to apply Indo-European linguistic categories to a non-IE languages.
I'd say that 可（以）is a "verb" (the description an action) here and 跟她约会 is an "object" (what is acted upon).
If you insist on assigning fixed "verb"/"object" etc labels (in IE sense) to Chinese "words" (character combos, really) and using these "words" only in those artificially fixed syntactic positions, you will encounter similar strangeness all the time. At least beyond the beginner level.
Chinese "words" are fluid with syntactic positions they can be used in, as verbs, objects and what not. In modern Chinese (白话）these "parts of speech" have become more rigid than in 文言文，but still far away from the rigidity on IE languages where they are fixed by morphology (as they are even in English).
Or perhaps your confusion is caused by misunderstanding of the whole SVO / typology thing. It is about overall sentence structure, not about phrase (shorter part) structure.
For me, 我 / 可以 / 跟她约会 is S / V / O, hopefully it is for everyone else too. Going into details, though:
我/PN 可以/VV 跟/P 她/PN 约会/VV
(NP (PN 我))
(VP (VV 可以)
(PP (P 跟)
(NP (PN 她)))
(VP (VV 约会))))))
可以跟他约会 is a completely regular verb phrase, and "verb phrases" are VO in Chinese. Yet 跟他约会 is another smaller "verb phrase" according to this parser (https://nlp.stanford.edu/software/lex-parser.shtml). Its rules fail here for all the reasons described in other responses - it's rather a "noun" phrase here.
Finally, for a bit of giggles on Chinese "words" and syntactic parsing, check this wonderful list. I lifted it from some book long ago, forgot which. I asked a few natives and they said only 3-4 sentences in this list read a bit stiff, but all are correct.